B + дерево с ключами переменной длины
В обычной реализации дерева B + мы можем предположить, что ключи имеют фиксированную длину (например, 25 байтов). Затем мы можем определить, что каждый узел должен иметь минимальное количество ключей и максимум.
Если бы я хотел, чтобы дерево принимало ключи переменной длины, что я должен изменить? Что если я скажу, что у узла должно быть как минимум 2 ключа, но ключ, который я пытаюсь вставить, настолько велик, что не помещается в блок, который содержит узел?
Решение
Простое решение состоит в том, чтобы хранить ключи как указатели (обернутые в тип, который переопределяет относительные операторы и т. Д.), А не как значения, но это, конечно, наносит ущерб месту, являющемуся частью использования B + деревьев.
Тем не менее, чем больше предметов, тем менее важно, что предметы находятся рядом в памяти. Огромные элементы не помещаются даже на страницу кеша, не говоря уже о нескольких на одной странице.
Другой относительно простой подход заключается в использовании типа объединения или размещения новых или чего-либо еще для выделения элементов в типе памяти для элемента, который достаточно велик для всех типов элементов, которые вы можете использовать. У вас все еще есть фиксированное количество байтов на элемент, но элементы не обязательно используют все эти байты.
Если вы готовы выполнить эту работу, у вас могут быть узлы переменного размера. Конечно, у вас будут проблемы с этими узлами, в зависимости от того, как вы организуете структуру данных в узле, чтобы справиться с этим. Например, в узле может быть небольшой массив указателей элементов, указывающих на элементы, которые также находятся внутри узла (отдельно не выделяются в куче).
Кроме того, каждый раз, когда вы меняете узел, вам может потребоваться перераспределить его. Даже если все, что вы делаете, это перебалансирование, это может переместить огромный элемент из одного узла в другой, и даже если у узла назначения есть место в смысле наличия свободного места для элемента, у него может не хватить байтов для хранения значение.
В некотором смысле, каждый узел был бы мини-кучей, в которой вы можете выделять или освобождать пространство для элементов, больших или малых, но иногда вам придется возвращаться к самой куче, чтобы заменить эту мини-кучу большей или меньшей. один.
Еще раз стоит упомянуть, что если элементы такие огромные, локальность внутри узла, вероятно, в любом случае не имеет значения.
Я реализовал многоканальные деревья в стиле B + в памяти перед собой, но я никогда не заходил в такую крайность.
Другие решения
Вы можете сохранить остаток большого ключа на странице переполнения, например там.
Используйте хеширование. Хеш — это фиксированное представление ключа. Для хороших функций хеширования см. http://www.cse.yorku.ca/~oz/hash.html.