Как определяется параметр n в B-деревьях и от чего зависит количество значений в узле

Что проверяют

Знаете ли вы, что у параметра B-дерева есть два распространённых определения, и понимаете ли, почему размер узла подгоняют под страницу диска. Следом обычно спрашивают, почему в базах данных используют B+-дерево и какой высоты получается индекс на миллионы строк.

Как отвечать

Сначала договоритесь о терминах, потому что учебники считают по-разному:

• минимальная степень t (Кормен): каждый узел, кроме корня, хранит от t - 1 до 2t - 1 ключей и имеет от t до 2t потомков, при t ≥ 2. В непустом дереве корню достаточно одного ключа;
• порядок m (Кнут): не больше m потомков и m - 1 ключей в узле, у внутреннего узла кроме корня не меньше ⌈m/2⌉ потомков. Дерево 2-3-4 это B-дерево порядка 4, оно же с t = 2;
• ключи и потомки: у внутреннего узла с k ключами ровно k + 1 потомков, ключи делят диапазон значений на промежутки.

Количество значений в узле определяет не алгоритм, а носитель. Узел читается с диска одной операцией, поэтому его размер равен странице: в PostgreSQL это 8 КБ, в InnoDB 16 КБ. Ёмкость узла примерно равна размеру страницы, делённому на размер ключа с указателем, так что чем короче ключ, тем больше ветвление. При ветвлении в несколько сотен дерево на миллиард записей обычно имеет четыре уровня, и поиск стоит считаных чтений страниц.

Нижняя граница заполнения держит баланс: переполненный узел делится пополам, а узел, где осталось меньше минимума ключей, занимает ключ у соседа или сливается с ним. Все листья лежат на одной глубине, поэтому поиск, вставка и удаление стоят O(log n).

Для Java полезно заметить, что TreeMap построен на красно-чёрном дереве. В оперативной памяти высокое ветвление не даёт выигрыша, а в дисковых хранилищах стандартом стало B+-дерево: значения только в листьях, листья связаны между собой для диапазонных запросов.

Где спотыкаются

Отвечают «в узле до n ключей», не уточнив определение. Дальше вся арифметика сдвигается на единицу.

Путают B-дерево с бинарным деревом поиска и считают, что буква B означает binary.

Не могут объяснить, зачем узлу сотни ключей. Ключ к ответу это стоимость чтения страницы с диска, а не число сравнений внутри узла.