B-tree / B+ tree

Пояснення Віктора «біля дошки», чому індекси баз даних — не бінарні дерева пошуку: BST над 100 млн рядків має глибину ~23 рівні, і при ~5 мс на дисковий seek така глибина фатальна. B-tree виправляють це, підганяючи розмір вузла під дисковий блок (8 КБ у Postgres/MySQL): кожен вузол отримує приблизно 200–2000 дітей, і дерево скорочується до ~4 чи навіть 2 рівнів (дерева й алгоритми пошуку). Насправді бази даних використовують B+ tree: дані живуть лише в листках, а листки зчеплені між собою по горизонталі, тож діапазонний скан на кшталт «ціна 100–110» іде ланцюжком листків замість повторного спуску деревом — саме тому за O(log n)-поведінкою, яку він бенчмаркає, стоять B+ tree, а не відсортовані масиви (навіщо алгоритми).

Нутрощі важать на практиці. У MySQL сама таблиця І Є B+ tree, відсортованим за первинним ключем (кластерний індекс), — ось чому вставки випадкових UUID термосять кешування вузлів дерева, тоді як послідовні auto-increment-вставки торкаються лише закешованих крайніх правих вузлів (індекси в MySQL і Postgres). Уперше він натякнув на це ще в оригінальному відео про індекси: індекс — це насправді B+ tree, а не простий BST, існують і хеш-індекси, а простий відсортований список теж працював би, але коштував би O(N) на підтримку (навіщо потрібні індекси).