Я изучаю возможность создания индивидуальной схемы хранения для моего приложения. Я думаю, что стоит потратить усилия на то, чтобы потенциально заново изобрести колесо, потому что производительность и эффективность хранения являются основной целью, а данные и операции с ним намного проще, чем все, что предоставляется СУБД (без обновлений, без удалений, предопределенный набор запросов
Я использую лишь небольшую горстку найденных мной веб-ресурсов о 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 + -Tree, высота 2 - внешние (листовые) узлы на уровне 2 содержат «фактические данные». Затем для вставки требуется разделение листового узла - листовой узел больше не содержит «фактических данных». Правильно ли я думаю, что с точки зрения реализации, поскольку данные могут иметь значительный размер, вы вместо этого храните своего рода `` указатель '' в качестве `` фактических данных '' - поэтому, если листовой узел становится узлом ветвления, этот указатель (из того же размера) вместо этого обновляется, чтобы указывать на новое поддерево?
Под этим я подразумеваю, что внутренние и внешние узлы, они должны быть действительно одного размера, поскольку внешние узлы могут стать внутренними, а перемешивание данных - не лучшая идея?
(Добавлен тег C #, так как я ' m реализует это с нуля на C #.)