Как сохранить инварианты B-дерева, когда элементы меняются по размеру?

Question

Для B-дерева порядка m каждый узел, кроме корня, должен содержать элементы от m-1 до 2m-1, где каждый элемент является, по меньшей мере, ключом и, возможно, также некоторыми дополнительными данными (например, значением). Однако каждый узел должен иметь определенный постоянный общий размер, чтобы обеспечить хорошую производительность на базовом блочном устройстве. Итак, что происходит, если ваши элементы имеют переменный размер?

SQLite3, похоже, имеет схему для прикрепления дополнительных узлов размера блока к своим узлам, а MySQL позволяет объявлять размер ваших записей (например, вы можете вводить свои поля не просто как строки, а строки под некоторым размером) , Какие существуют другие решения? И о чем люди думают, когда выбирают друг друга?

редактировать: И в предыдущем предложении, я имею в виду, что же разработчики баз данных думать о том, когда решив реализовать свои B-деревья один путь над другим?

(я в курсе баз данных прямо сейчас, так что я больше заинтересован в теории и конструкции угол, чем в деталях конкретных систем.)

Answer 1

Я думаю, что это довольно хороший вопрос. Хотя у поставщиков RDBMS есть несколько разные реализации, базовая теория такая же, и я сомневаюсь, что кто-то использует реализации b-tree как определяющий фактор при выборе поставщика.

Как я понимаю, базовая структура каждой страницы b-дерева содержит ключи и указатели. Указатели постоянно ссылаются на другие страницы, содержащие больше ключей и указателей, с последним указателем, ссылающимся на связанную запись данных.

Как обращаться с ключами переменной длины является интересным. Возможно, другие могут пролить свет на конкретные решения поставщика.

Answer 2

Я знаю, что SQL Server может иметь длину ключа до 900 байт при размере страницы 8192 байта. Если у вас на самом деле есть ключи 900 байт, только 9 (или 8) строк будут помещаться на страницы промежуточного уровня индекса. Это означает, что коэффициент ветвления ниже обычного. Это может нарушить теоретический инвариант B-дерева, но это всего лишь академическая проблема, которая не мешает производительности значительным образом. Это не меняет асимптотической сложности используемых алгоритмов.

Вкратце: это чисто академическая проблема.