Какая особенность B-Tree связана с физической реализацией
Что проверяют
Понимаете ли вы, почему в базах используют B-дерево, а не бинарное дерево поиска, хотя асимптотика у них одна. Следом часто спрашивают про отличие B+tree и про то, почему случайные ключи вроде UUIDv4 портят индекс.
Как отвечать
Главная особенность: узел дерева равен странице диска, то есть блоку, который читается за одну операцию ввода-вывода. В PostgreSQL страница 8 КБ, в InnoDB 16 КБ. В такой узел помещаются сотни ключей, поэтому ветвление огромное, а дерево низкое.
- высота: при ветвлении около 500 три уровня адресуют больше ста миллионов ключей. Поиск это три-четыре чтения страниц, причём верхние уровни почти всегда лежат в кеше;
- стоимость меряют чтениями страниц, а не сравнениями: внутри узла идёт бинарный поиск в памяти, он почти бесплатен по сравнению с чтением с диска;
- балансировка через разбиение: переполненный узел делится пополам, средний ключ поднимается к родителю. Новый уровень появляется только при разбиении корня, поэтому все листья всегда на одной глубине;
- B+tree: в реальных СУБД данные или ссылки на строки лежат только в листьях, а листья связаны списком. Во внутренних узлах остаются одни ключи, ветвление ещё выше, а диапазонный запрос идёт по соседним листьям без подъёма к корню.
Для Go-разработчика стоит добавить, что та же идея работает в памяти: узел с десятками ключей в непрерывном массиве дружит с кешем процессора лучше, чем бинарное дерево с указателем на каждый элемент. На этом построена библиотека github.com/google/btree, а встраиваемое хранилище bbolt держит данные в B+tree на страницах, отображённых в память через mmap.
Где спотыкаются
Говорят только про O(log n) и балансировку. Это верно и для красно-чёрного дерева, а вопрос как раз про страницы и число обращений к диску.
Путают B-tree и B+tree или не знают, что индексы в PostgreSQL и InnoDB устроены как B+tree со связанными листьями.
Не знают про разбиения страниц: при вставке случайных ключей новые значения попадают в середину дерева, страницы делятся, индекс раздувается и хуже кешируется. Последовательные ключи, например автоинкремент или UUIDv7, дописываются в правый край.