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

Ответ 1

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

Повторяющиеся клавиши

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

[Обновление]

Есть шанс забыть ключ:

Node N [L1 | 3 | L2] Лист L1 [1,2,3] → L2 [3, 4, 5]

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

Node N [L1 | 3 | L2] Лист L1 [1,2,3] → L2 [4, 5]

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

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

Node N [L1 | 4 | L2] Лист L1 [1,2,3] → L2 [4, 5]

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

Node N [L1 | 3 | L2] Лист L1 [1,2] → L2 [3, 4, 5]

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

Ответ 4

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

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

Node parents: ключ до первого ключа в дочернем node находится в родительском node.

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

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

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

(Действительно) Дублирующие клавиши

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

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