Как устроен алгоритм B-tree
Что проверяют
Понимание, зачем нужна структура с большим ветвлением, если уже есть сбалансированные бинарные деревья. Хороший ответ связывает размер узла с размером страницы диска и количеством операций ввода-вывода.
Как отвечать
B-tree это сбалансированное дерево поиска, где узел хранит много ключей и имеет много детей. Через минимальную степень t (формулировка CLRS):
- в узле от t-1 до 2t-1 ключей, у узла с k ключами ровно k+1 детей;
- корень непустого дерева может содержать всего 1 ключ;
- все листья на одном уровне, дерево растёт вверх через расщепление корня;
- высота порядка log по основанию t от n.
Смысл именно в t. Узел подбирают под страницу хранилища (в InnoDB это 16 КБ), поэтому в него влезают сотни ключей. При ветвлении 200 дерево на 100 млн записей имеет высоту 4: четыре чтения страницы вместо примерно 27 у красно-чёрного дерева. Сравнения внутри узла почти бесплатны на фоне стоимости чтения страницы, и это единственное настоящее обоснование структуры.
Операции:
- Поиск: бинарным поиском находим позицию в узле, спускаемся в нужного ребёнка.
- Вставка: доходим до листа и вставляем. Переполненный узел делится надвое, медианный ключ поднимается в родителя. Каскад делений может дойти до корня, тогда создаётся новый корень и высота растёт на единицу. Классическая реализация расщепляет полные узлы упреждающе на спуске, за один проход.
- Удаление: если в узле осталось меньше t-1 ключей, он занимает ключ у соседа через родителя либо сливается с соседом. Удаление из внутреннего узла сводится к удалению предшественника или преемника из листа.
Чем отличаться от учебника: базы данных используют не чистое B-tree, а B+ tree. Значения лежат только в листьях, внутренние узлы содержат лишь разделяющие ключи, а листья связаны в список. Отсюда более высокий фанаут верхних уровней и дешёвый диапазонный скан (BETWEEN, ORDER BY ... LIMIT), который в чистом B-tree требовал бы обхода дерева. InnoDB и PostgreSQL (там это вариант B-link tree, устойчивый к конкурентному доступу) устроены именно так, хотя в SQL тип индекса называется BTREE.
Полезно назвать ограничения: индекс работает на префиксе составного ключа и на диапазонах, но бесполезен для LIKE '%x'; случайные вставки в середину дают расщепления и фрагментацию страниц, а монотонно растущий ключ ложится плотно; для нагрузки с преобладанием записи альтернативой служит LSM-дерево.
Где спотыкаются
Путают B-tree и B+ tree и уверенно заявляют, что в MySQL данные лежат во всех узлах. Второй промах: не объясняют, почему логарифм с большим основанием выгоднее, и сводят ответ к формуле «дерево самобалансирующееся».