B + дерево с ключами переменной длины

В обычной реализации дерева B + мы можем предположить, что ключи имеют фиксированную длину (например, 25 байтов). Затем мы можем определить, что каждый узел должен иметь минимальное количество ключей и максимум.

Если бы я хотел, чтобы дерево принимало ключи переменной длины, что я должен изменить? Что если я скажу, что у узла должно быть как минимум 2 ключа, но ключ, который я пытаюсь вставить, настолько велик, что не помещается в блок, который содержит узел?

4

Решение

Простое решение состоит в том, чтобы хранить ключи как указатели (обернутые в тип, который переопределяет относительные операторы и т. Д.), А не как значения, но это, конечно, наносит ущерб месту, являющемуся частью использования B + деревьев.

Тем не менее, чем больше предметов, тем менее важно, что предметы находятся рядом в памяти. Огромные элементы не помещаются даже на страницу кеша, не говоря уже о нескольких на одной странице.

Другой относительно простой подход заключается в использовании типа объединения или размещения новых или чего-либо еще для выделения элементов в типе памяти для элемента, который достаточно велик для всех типов элементов, которые вы можете использовать. У вас все еще есть фиксированное количество байтов на элемент, но элементы не обязательно используют все эти байты.

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

Кроме того, каждый раз, когда вы меняете узел, вам может потребоваться перераспределить его. Даже если все, что вы делаете, это перебалансирование, это может переместить огромный элемент из одного узла в другой, и даже если у узла назначения есть место в смысле наличия свободного места для элемента, у него может не хватить байтов для хранения значение.

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

Еще раз стоит упомянуть, что если элементы такие огромные, локальность внутри узла, вероятно, в любом случае не имеет значения.

Я реализовал многоканальные деревья в стиле B + в памяти перед собой, но я никогда не заходил в такую ​​крайность.

2

Другие решения

Вы можете сохранить остаток большого ключа на странице переполнения, например там.

1

Используйте хеширование. Хеш — это фиксированное представление ключа. Для хороших функций хеширования см. http://www.cse.yorku.ca/~oz/hash.html.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector