B-дерево: почему индексы БД живут на диске так

Если ты понимаешь, почему на диске цена - это число чтений блоков (высота), почему узел B-дерева делают размером с блок (сотни ключей) и почему это даёт высоту 3-4 на миллиардах ключей, листай до «Теперь сам».

Как думаешь, что дорого, когда данных больше, чем памяти

Всё, что мы считали до сих пор, предполагало данные В ПАМЯТИ, где любое сравнение стоит примерно одинаково. Но индекс базы данных - это гигабайты, он лежит на ДИСКЕ. А диск устроен иначе: прочитать один байт нельзя - читается сразу целый БЛОК (страница), и это чтение чудовищно медленное по меркам процессора (миллионы тактов против единиц). Значит на диске «дорого» - это не сравнение и не арифметика, а само ОБРАЩЕНИЕ К ДИСКУ. Красно-чёрное дерево на миллиард ключей имеет высоту ~30 - это ~30 чтений диска на один поиск, и каждое чтение вытягивает целый блок, из которого мы используем один узел. Расточительно. Раз блок всё равно читается целиком - надо НАБИТЬ в него как можно больше ключей.

На что это похоже

Библиотека, где заказ книги с дальнего склада едет час, а полистать её на столе - секунды. Глупо заказывать книги по одной, если можно одним рейсом привезти целую ТЕЛЕЖКУ. Ты просишь сразу коробку каталожных карточек (блок), просматриваешь все за столом (в памяти - быстро) и лишь изредка заказываешь следующую коробку (чтение диска - долго). Чем больше карточек в коробке, тем меньше рейсов на склад. B-дерево так и устроено: узел - это «коробка» размером с то, что диск привозит за один рейс, и в неё кладут максимум ключей, чтобы рейсов (высоты) было как можно меньше.

Механизм: узел = блок, ветвление в сотни раз

B-дерево порядка t (минимальная степень): узел хранит от t−1 до 2t−1 ключей и от t до 2t детей (кроме корня). На практике t подбирают так, чтобы узел ЗАПОЛНЯЛ дисковый блок:

дисковый блок ~ 4-16 КБ
ключ + указатель ~ несколько десятков байт
=> в узел влезает порядка 100-1000 ключей
=> ветвление (число детей) ~ 100-1000 на КАЖДОМ уровне

Всё как в 2-3 дереве, только «широкое»: поиск спускается от корня, на каждом узле выбирая нужный из сотен диапазонов; вставка идёт в лист, переполнение расщепляет узел и поднимает средний ключ; листья всегда на одном уровне. Но теперь оценка высоты другая. При ветвлении b на уровень дерево из n ключей имеет высоту ≈ log_b(n):

b = 256, n = миллиард:  log_256(10^9) ≈ 3.7  →  высота 3-4
для сравнения log_2(10^9) ≈ 30

Число ЧТЕНИЙ ДИСКА на поиск = высота = 3-4 вместо 30. Внутри узла ключи ищут в памяти (двоичным поиском) - это «бесплатно» на фоне чтения блока.

Правило

B-дерево - многоключевое сбалансированное дерево, где узел размером с ДИСКОВЫЙ БЛОК хранит сотни ключей и ветвится в сотни раз. Оно живёт на диске, где цена - число ЧТЕНИЙ БЛОКОВ, то есть ВЫСОТА. Высокое ветвление b даёт высоту ≈ log_b(n) - крошечную: миллиарды ключей укладываются в 3-4 уровня, значит поиск - 3-4 обращения к диску. Внутри узла ключи ищут в памяти (дёшево). Балансировка - как в 2-3 дереве: вставка в лист, расщепление переполненных, все листья на одном уровне. На B-деревьях стоят индексы баз данных и файловые системы.

Разбор: почему считают чтения диска, а не сравнения

Вся конструкция B-дерева следует из одного факта: на диске операции НЕ равноценны. В памяти сравнение и чтение стоят примерно одинаково, поэтому там оптимизируют число сравнений (log₂ n). На диске одно чтение блока - это миллионы тактов (механическое позиционирование у HDD, задержки контроллера у SSD), а сравнение ключей уже в прочитанном блоке - единицы тактов. Разница в миллионы раз. Значит правильная «стоимость» - это число обращений к диску, а всё, что происходит ВНУТРИ прочитанного блока, практически бесплатно. Отсюда стратегия: минимизировать число уровней (высоту), даже ценой того, что внутри узла придётся просмотреть сотни ключей - эти просмотры идут в памяти и не в счёт. B-дерево доводит эту логику до предела: набивает узел под завязку блоком, чтобы каждый спуск на уровень «окупал» дорогое чтение максимумом информации. Это тот же принцип, что локальность памяти и кеш в разделе про массивы, только на уровне «память против диска» - иерархия та же, просто разрыв в скорости ещё больше.

Разбор: почему высота выходит 3-4, а не 30

Всё решает основание логарифма. Высота дерева с ветвлением b на n ключей - это log_b(n), а не log₂(n). У двоичного дерева b = 2, поэтому log₂(10^9) ≈ 30 уровней. У B-дерева b доходит до сотен: при b = 256 высота log_256(10^9) = log₂(10^9)/log₂(256) = 30/8 ≈ 3.7 - около четырёх уровней. Ветвление входит в ЗНАМЕНАТЕЛЬ через свой логарифм: высота делится на log₂ b, а не на b. Увеличив ветвление с 2 до 256, мы поделили высоту на 8 - с 30 до 4. А высота на диске = число медленных чтений, поэтому поиск ускорился в те же ~8 раз (и это ещё до учёта того, что верхние 1-2 уровня обычно закешированы в памяти - тогда реальных чтений диска всего 1-2). Вот почему индексы делают именно B-деревьями, а не красно-чёрными: на диске важна не глубина в сравнениях, а глубина в БЛОКАХ, и широкий узел её минимизирует.

Что ломается без этого

Первая ошибка - использовать двоичное дерево (красно-чёрное) для дискового индекса: высота ~30 даст ~30 чтений диска на поиск вместо 3-4 - в разы медленнее, хотя в ПАМЯТИ оно ничем не хуже. На диске нужен широкий узел. Вторая - делать узел B-дерева произвольного размера, не привязанного к блоку: слишком мелкий узел теряет весь смысл (мало ветвления, высокое дерево), слишком крупный - читается за несколько блоков; узел подгоняют ПОД размер блока. Третья - считать стоимость поиска в сравнениях, а не в чтениях блоков: тогда B-дерево кажется «медленнее» (внутри узла сотни сравнений), хотя на диске оно кратно быстрее - сравнения в памяти почти бесплатны. Четвёртая - путать B-дерево и B+-дерево: в B+-дереве все ДАННЫЕ в листьях, а листья связаны в список для быстрых диапазонных сканов - это распространённый в БД вариант, но идея та же.

Зачем это в работе

B-деревья (и их вариант B+-деревья) - фундамент хранения данных: индексы во ВСЕХ реляционных базах (PostgreSQL, MySQL, Oracle), ключи в файловых системах (NTFS, ext4, HFS+), встраиваемые хранилища (SQLite, BerkeleyDB). Когда ты создаёшь индекс в базе и запрос по нему летает - это B-дерево свело поиск среди миллиардов строк к 3-4 чтениям диска. Понимать B-дерево - значит понимать, ПОЧЕМУ индекс ускоряет запрос (высота вместо полного скана), почему он занимает место (хранит копию ключей в дереве), почему диапазонные запросы WHERE x BETWEEN a AND b по индексу дёшевы (спуск + обход листьев по порядку) и почему структура данных для диска устроена иначе, чем для памяти. Это прямое применение всего раздела: то же дерево поиска, та же балансировка, но цена операции переопределена под реальное железо - и оптимум сместился к широким узлам. Умение видеть, что «стоимость» зависит от уровня памяти (кеш, ОЗУ, диск, сеть), и подбирать структуру под неё - одна из самых практичных идей курса.

Теперь сам

Индекс на n = 10^9 ключей. Оцени высоту (число чтений диска на поиск) для двоичного дерева и для B-дерева с ветвлением 200. Во сколько раз B-дерево быстрее по обращениям к диску?