B-Trees / B + Trees и повторяющиеся ключи

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

Я использую лишь небольшую горстку найденных мной веб-ресурсов о B-деревьях и B + -деревьях - Википедия, http://www.bluerwhite.org/btree/ , http://slady.net/java/bt/view.php , http://www.brpreiss.com/books/opus6/html/page342.html (последний один является наиболее ценным).

Дублирующиеся ключи

Первая проблема, которую я пытаюсь решить, - это как работать с повторяющимися ключами - это дерево будет действовать как индекс БД и, например, не будет просто одна «вещь» с «color = red», поэтому поиск «красного» в этом дереве должен дать много результатов.

На данный момент я придумал два решения. Первый - это просто наличие нескольких записей в дереве для каждого из них. Но когда в дереве 100 000 или 1 000 000 «красных» элементов ... очень ли это эффективно для древовидной структуры? Второй должен был иметь только одну запись для каждого ключа, но «полезная нагрузка», связанная с каждым ключом, указывает на другой блок данных, который представляет собой связанный список, указывающий на все экземпляры элементов, которые являются «красными».

Is есть ли общий / лучший вариант?

B + Узлы дерева меняют типы

Я хотел проверить свое предположение. Скажем, у вас есть B + -Tree, высота 2 - внешние (листовые) узлы на уровне 2 содержат «фактические данные». Затем для вставки требуется разделение листового узла - листовой узел больше не содержит «фактических данных». Правильно ли я думаю, что с точки зрения реализации, поскольку данные могут иметь значительный размер, вы вместо этого храните своего рода `` указатель '' в качестве `` фактических данных '' - поэтому, если листовой узел становится узлом ветвления, этот указатель (из того же размера) вместо этого обновляется, чтобы указывать на новое поддерево?

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

(Добавлен тег C #, так как я ' m реализует это с нуля на C #.)

12
задан animuson 19 August 2012 в 20:32
поделиться