B-деревья: Математика файловых систем и баз данных
При изучении структур данных студенты первым делом знакомятся с бинарными деревьями поиска. Они отлично работают, пока все данные помещаются в оперативной памяти компьютера (RAM). Но что происходит, когда нам нужно проиндексировать терабайтную базу данных, хранящуюся на медленном жестком диске? Здесь законы эффективности кардинально меняются. Дискретная математика решает проблему долгих дисковых операций с помощью специализированной структуры — B-дерева.
Главная проблема жестких дисков (HDD) и даже современных SSD — это высокая латентность доступа. Операционная система не читает данные с диска по одному байту; она считывает информацию целыми блоками, называемыми страницами (обычно размером 4 КБ или 8 КБ). Если мы используем классическое бинарное дерево, каждый переход от родителя к потомку может потребовать загрузки новой страницы с диска. Для дерева с миллионом записей поиск элемента потребует около 20 дисковых чтений, что катастрофически замедлит работу базы данных.
В 1970 году Рудольф Байер и Эдвард МакКрейт изобрели B-дерево (B-tree). Это сильно ветвящееся самобалансирующееся дерево поиска. В отличие от бинарного дерева, каждый узел B-дерева содержит не один ключ, а целый массив отсортированных ключей (сотни или даже тысячи), и имеет множество дочерних указателей. Размер одного узла строго подгоняется под физический размер дисковой страницы.
Математические свойства B-дерева порядка m:
- Каждый внутренний узел содержит от ⌈m/2⌉ до m потомков (за исключением корня).
- Узел, имеющий k потомков, содержит ровно k-1 ключей, которые разделяют данные на диапазоны для навигации.
- Все листовые узлы всегда находятся на одном, самом нижнем уровне (идеальная сбалансированность).
Благодаря огромному коэффициенту ветвления, B-дерево получается невероятно "широким" и "низким". Дерево глубиной всего в 3 или 4 уровня способно проиндексировать миллиарды записей. Это означает, что для поиска любой строки в гигантской базе данных потребуется всего 3-4 обращения к жесткому диску!
В современных СУБД (PostgreSQL, MySQL, SQLite) и файловых системах (NTFS, ext4) используется усовершенствованная модификация — B+ дерево (B+ tree). В нем внутренние узлы хранят исключительно ключи для навигации, а сами полезные данные (или указатели на строки таблицы) лежат только в листьях. Более того, все листья связаны друг с другом в двусвязный список. Это позволяет СУБД не только мгновенно находить конкретную запись (точечный запрос), но и невероятно быстро выгружать данные диапазонами (запросы типа WHERE price BETWEEN 100 AND 500), просто двигаясь по ссылкам между листьями.
