Стендап Сьогодні
📢
Канал в Telegram @stendap_sogodni
🦣
@stendap_sogodni@shevtsov.me в Федиверсі
24.12.2025
Що ж воно таке за дерево той індекс?
ОК, давайте відразу виправлюсь: все ж індекси використовують Б-дерева, а не двійкові дерева. Але в чому різниця?
Двійкове дерево то є просто дерево, де в кожного вузла не більше двох дітей. Є двійкові дерева пошуку, де ці діти (піддерева) містять"елементи менші за поточний" та “більші”. Є збалансовані дерева, де піддерева мають рівний (чи приблизно рівний) розмір. (Бо наївна побудова дерева може дати зовсім не рівний та не ефективний результат.)
А Б-дерево — це як збалансоване двійкове дерево пошуку, тільки замість того щоб тримати в кожному вузлі тільки один елемент, тепер їх стає N - та так само як у двійковому дереві, ці елементи ділять простір пошуку на піддерева — але їх вже не два, а N+1. Відповідно, дерево стає “щільнішим”, вузлів в ньому стає менше, як і глибини.
А чому, власне, взагалі для пошуку беруть дерева, а не щось інше? Бо за деревом можна не тільки швидко шукати, а й швидко вносити зміни. (Швидко — це зі складністю O(log N).) Б-дерева саме й винайшли для прискорення пошуку у великих файлах. Причому з такою вимогою, щоб можна було завантажувати в памʼять лише частину дерева.
Б-дерева настільки прижилися, що зустрічаються майже в будь-якій базі даних. Їх можна знайти й у звичайних структурах даних різних мов - JavaScript, Go, Rust тощо. Трохи кумедно, що вони здаються складнішою структурою, втім насправді ми користуємося ними постійно — за лаштунками простих абстракцій.