B-Trees / B + Деревья и дубликаты ключей

Question

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

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

Дубликаты ключей

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

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

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

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

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

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

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

Answer 1

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

Что касается первой части вашего вопроса, когда вы удаляете запись данных из БД, вам нужно будет найти все ключи, которые указывают на эту конкретную запись, и удалить их. Если для этого вам нужно просмотреть длинные линейные списки, удаление будет медленным. Я предполагаю, что вы используете двоичный поиск в узле, чтобы быстро найти правильный элемент узла (ключ + указатель), поэтому, если вы сделаете так, чтобы механизм «поиска узла» включал возможность запрашивать конкретную комбинацию клавиш + указатель Вы можете быстро найти правильный ключевой элемент для удаления. Другими словами, сделайте указатель записи данных частью поиска (только при поиске ключа определенной записи данных). Это означает, что дубликаты ключей будут храниться в узлах в порядке «указатель данных», поэтому, если порядок дублирования ключей не важен, этот механизм будет работать.

Answer 2

Попытка ответить на мой собственный вопрос .. Я также приветствовал бы другие ответы.

Дубликаты ключей

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

B + Узлы дерева, смена типов

В памяти мои узлы имеют ссылку object, которая может указывать на другой узел (сам по себе другой действительный B + Tree) в случае внутреннего / ответвленного узла, или на данные, непосредственно в случае внешний / листовой узел. На диске это будет работать очень схожим образом: 64-битное значение для каждого «слота связи», как я их назвал, - либо смещение в файле, если оно указывает на подузел, либо номер блока. если указывает на данные напрямую (или на заголовок связанного списка в случае, упомянутом в первой части вопроса).

Answer 3

Основная особенность деревьев B + - минимизация поиска диска.Если вы просто «храните указатели», то вы теряете эту выгоду, и ваш код будет преследовать файловые указатели, и вы будете искать головку диска повсюду.Вы не можете прочитать сто байтов с диска, все чтения и записи находятся в выровненных блоках.

Конечные родители: данные всегда находятся в листе, и только один ключ на лист находится в узлах (которые являются непосредственнымиуходит из листьев).Узел позволяет вам «просмотреть» содержимое листа, посмотрев копию первого ключа в этом листе, прямо там, в узле.

Родители узла: ключ перед первым ключом в дочернем узлев родительском узле.

Дублирование данных не плохо.Например, если на листе имеется 207 записей, а на узел приходится 268 записей, то вы будете хранить один дополнительный ключ на каждые 207 записей.Если у вас более 207 * 269 листов, вам понадобится еще один ключ на 207 * 269 записей.

Кажется, вы путаете B-деревья и B + деревья.В деревьях B + всегда есть данные в листьях, а в узлах никогда не бывает данных.Только образец самого низкого ключа для дочернего элемента присутствует в узле.Данные никогда не «перемещаются» вверх по дереву B +, только копии одного нижнего ключа на каждого потомка распространяются вверх.

Накладные расходы растут логарифмически.Минимальное дублирование экономит много поисков.

(Действительно) Дубликаты ключей

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

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

Answer 4

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

Поскольку лист группирует все ключи вместе, вам просто нужно пройтись по листу влево (позиция -1), чтобы найти первую запись с данным ключом. Если вы найдете первый ключ листа, вам нужно проверить предыдущие листы.

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

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

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

---

для высокой вероятности дубликатов лучше всего искать другую модель хранения, храня ключ -> данные. Особенно если данные меняются не часто.

[Update]

Существует вероятность забыть ключ:

Узел N [L1 | 3 | L2] Лист L1 [1,2,3] -> L2 [3, 4, 5]

Вы удаляете 3 в L2, в результате чего вы.

Узел N [L1 | 3 | L2] Лист L1 [1,2,3] -> L2 [4, 5]

Когда вы сейчас ищете, вы обнаружите, что 3 не в L2. Теперь вы можете заглянуть в предыдущий лист, чтобы найти 3.

Другой способ - обновить ключ до фактического первого ключа листа, в результате чего (возможно, будет получено распространение обновления):

Узел N [L1 | 4 | L2] Лист L1 [1,2,3] -> L2 [4, 5]

Или вы заимствуете из левого листа элемент.

Узел N [L1 | 3 | L2] Лист L1 [1,2] -> L2 [3, 4, 5]

Я склонен использовать первое решение, так как оно работает также для листьев в середине многолистных дубликатов.