B-Дерева: Індекс, що стоїть за кожною базою даних

Дерево, створене для повільного зберігання

Чорно-біле дерево оптимізоване для мінімізації порівнянь у пам’яті. Б-дерево (Байєр і МакКрейт, 1972) оптимізоване для чогось зовсім іншого: мінімізації кількості дискових операцій читання, які значно повільніші за будь-які порівняння в пам’яті. Замість одного ключа на вузол, Б-дерево порядку m містить багато ключів у кожному вузлі – достатньо, щоб заповнити точно одну дискову сторінку або кеш-лінію, тому що одна повільна операція читання одночасно витягує інформацію на тисячі порівнянь.

order m B-tree, every non-root node holds:
  between ceil(m/2) - 1  and  m - 1   keys
  between ceil(m/2)      and  m       children (internal nodes)

keys inside a node are sorted; the k+1 children of a node with k keys
"straddle" the k keys, so child[i] holds keys strictly between
key[i-1] and key[i]

Вставка: заповнення, розділення біля медіани, підняття

Новий ключ вставляється у відповідний лист, зберігаючи його відсортованість. Якщо цей лист тепер містить m ключів – на один занадто багато – він ділиться: середній ключ переміщується до батьківського вузла, а ключі з обох боків від нього стають двома окремими частково повними вузлами.

insert(ключ): лист = find_leaf(ключ) вставити ключ у лист, зберігаючи його відсортованість while лист.keyCount == m: // переповнено, потрібно розділити mid = лист.keys[m / 2] // середній ключ лівий, правий = розділити лист навколо mid якщо у листа немає батьківського вузла: створити новий корінь з mid, діти [лівий, правий] // дерево зростає на рівень +1 інакше: вставити mid у лист.parent, замінити лист на [лівий, правий] лист = лист.parent // розділення може поширюватися вгору Ключовим моментом є те, що B-дерево росте лише вгору, шляхом розділення кореня, тому кожен лист завжди знаходиться на абсолютно тій самій глибині – немає листа, який глибший за інший, на відміну від незбалансованого бінарного дерева.

insert(key):
  leaf = find_leaf(key)
  insert key into leaf, keeping it sorted
  while leaf.keyCount == m:               // overfull, must split
    mid = leaf.keys[m / 2]                 // median key
    left, right = split leaf around mid
    if leaf has no parent:
      create new root with mid, children [left, right]  // tree grows +1 level
    else:
      insert mid into leaf.parent, replace leaf with [left, right]
      leaf = leaf.parent                   // the split may cascade upward

Чому висота майже не має відношення до логарифмічного

Висота B-дерева становить O(log_m n), де основа логарифма – це розгалужувальний фактор m, а не 2. Червоно-чорне дерево з мільйоном ключів має висоту приблизно 2·log2(1,000,000) ≈ 40. B-дерево порядку 200, що зберігає той самий мільйон ключів, має висоту приблизно log_200(1,000,000) ≈ 2,6 – практично 3 рівні. Ця різниця є основною причиною існування B-дерев: при достатньо великому m, що відповідає розміру дискової сторінки або кеш-лінії, будь-яку базу даних з мільйонами або мільярдами рядків можна шукати в 3 або 4 дискових операціях читання, а верхні один чи два рівні зазвичай залишаються постійно кешованими в RAM, що робить більшість пошуків більш дешевими на практиці.

B+ дерева та B* дерева

Майже жодна виробнича база даних не використовує простий B-дерево; майже всі використовують B+ дерево. Різниця полягає в тому, що внутрішні вузли B+ дерева зберігають копії ключів лише для маршрутизації пошуків, тоді як весь фактичний обсяг даних знаходиться в листах, а листки з'єднані ланцюжком. Цей ланцюжок перетворює запит відсоркованого діапазону — "надати всі рядки між X та Y" — на одноразову прогулянку деревом разом із швидким боковим ходом по пов’язаних листах, замість повторних повних проходів дерева. B* дерево йде ще далі, відкладаючи розщеплення: коли вузол переповнюється, він спочатку намагається перерозподілити ключі з сусідом, лише тоді, коли обидва сусідні вузли також повні, і розділяє два повні вузли на три вузли, частково заповнені третиною, замість двох вузлів, частково заповнених. Це зберігає вузли більш повною (приблизно 2/3 замість 1/2) за рахунок більшої складності вставки.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте B-Trees і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.