В прошлых постах мы с тобой разобрали страницы (👉 раз), увидели, как индекс спасает от Seq Scan (👉 два), и пощупали B-дерево изнутри — корень, разделители, листья (👉 три). Дальше разберёмся, что значит «B», чем B+-дерево отличается от B-дерева, как оно держит себя ровным, и какая сложность поиска по нему🔎
🔤 Что значит 🅱️
Точного ответа нет💁 Структуру B-дерева придумали Рудольф Байер и Эдвард МакКрейт в Boeing Research Labs в начале 70-х, но что означает B — авторы так и не объяснили. Варианты: Balanced, Bayer (фамилия), Boeing (фирма), а ещё broad, bushy, и даже between. По воспоминаниям МакКрейта, Байер шутил: «чем больше думаешь, что значит B в B-tree, тем лучше понимаешь B-tree» (по крайней мере, такая история в вики). Так что «B = balanced» — логичное предположение, но оно не подтверждено разработчиками¯\_(ツ)_/¯
➕ А вот «+» — уже не загадка
Это и есть главное отличие от классического B-дерева, в котором данные могут находиться как во внутренних узлах, так и в листовых. B+-tree, на котором основаны индексы в популярных СУБД (PostgreSQL, MySQL, MongoDB, SQL Server), устроено немного иначе:
🟢 Данные (в случае PostgreSQL,
ctid — указатели на строки) живут только в листьях. Внутренние узлы хранят одни ключи-разделители: чистое «оглавление», маршрут до листа. Те самые «≥ 367 → блок 2» из этого поста.🟢 Листья сцеплены в связный список. Поэтому поиск по диапазонам (
>, <, BETWEEN) работает достаточно быстро: спустился до листьев и побежал по ним подряд, не возвращаясь наверх (см. дикпик 3). Тот же список бесплатно даёт и упорядоченный обход: ORDER BY может выполняться через последовательный обход индекса без дополнительной сортировки (но оптимизатор не всегда выбирает индексный проход). В классическом B-дереве упорядоченный обход тоже возможен, но для перехода к следующему ключу приходится регулярно возвращаться к внутренним узлам дерева. В B+-дереве листья уже связаны между собой, поэтому диапазонные запросы и последовательный обход выполняются проще и эффективнее📈
И ещё 🅱️онус: благодаря тому, что внутренние узлы хранят только ключи-разделители, они компактнее → в страницу 8 KB влезает больше разделителей → ветвление выше → уровней дерева меньше → меньше чтений с диска.
Насколько степень ветвления выше? В 8 KB-страницу влезают сотни мелких элементов. В листе элемент — это «ключ +
ctid» (для int их 366, см. этот пост). А во внутреннем узле элемент — «ключ-разделитель + ссылка на дочернюю страницу», и таких ссылок тоже сотни, то есть сотни веток к дочерним узлам (см. дикпик 2). Для сравнения, двоичные деревья (AVL, красно-чёрные) имеют всего по две ветви, из-за чего они высокие и заточены скорее под оперативную память, а не под диск, поэтому как основу для дисковых индексов их обычно не используют.
🧰 Как это использовать
🔹 «B» — историческая загадка, а «+» — это «данные только в листьях + листья связаны в список».
🔹 Индекс по столбцу ускоряет не только поиск по равенству, но и диапазоны (>, <, BETWEEN): БД спускается к началу диапазона и идёт по связанным листьям. Часто фильтруешь по диапазону — индекс окупается.
🔹 ORDER BY по индексируемому столбцу может пройти без отдельной сортировки, если порядок в запросе совпадает с порядком индекса. Повод согласовать ORDER BY с порядком столбцов в индексе.
🔹 Один B+-tree-индекс закрывает сразу три сценария: точечный поиск, диапазон и сортировку — поэтому индекс по «горячему» столбцу часто полезнее, чем кажется.
🧑💻dp 🥁
#бд #postgresql #инженерныештучки #heavywednesday