Каковы различия между B-деревом и B * -деревом, кроме требования к полноте?

Question

Я знаю о этом вопросе, но о B-дереве и B + -дереве . Извините, если есть подобное для B*-tree, но я не смог найти такое.

---

Итак, в чем разница между этими двумя деревьями? статья в Википедии о B*-trees очень короткая.

Единственная разница, которая здесь отмечена, это "non-root nodes to be at least 2/3 full instead of 1/2". Но я предполагаю, что есть кое-что еще .. Может быть только один вид дерева - B-tree, только с разными константами (для полноты каждого некорневого узла), и не может быть двух разных деревьев, если бы это было единственное отличие , верно?

Кроме того, еще одна вещь, которая заставила меня задуматься о большем количестве различий:

"A B*-tree should not be confused with a B+ tree, which is one where the 
leaf nodes of the tree are chained together in the form of a linked list"

Итак, B+-tree имеет что-то действительно конкретное - связанный список. Какая особенность B*-tree, или ее нет?

---

Кроме того, в статье википедии нет внешних ссылок / ссылок. Есть ли какие-либо ресурсы вообще? Статьи, учебники, что-нибудь?

Спасибо!

Answer 1

Отредактировано Без разницы, кроме мин. коэффициент заполнения.

Страница № 489

Из вышеприведенной книги

B ^* - tree - это вариант B-дерева, который требует, чтобы каждый внутренний узел был заполнен как минимум на 2/3, а не на минимум наполовину.

Кнут также определяет дерево B * именно так (Искусство компьютерного программирования, том 3).

" Вездесущее B-дерево " имеет целый подраздел на B ^* - деревьев . Здесь Комер определяет дерево B ^* - точно так же, как Кнут и Кормент и др. делать, но также разъясняет, откуда возникает путаница - B ^* - tree алгоритмы поиска по дереву и некоторые безымянные варианты B-дерева, разработанные Кнутом, которые теперь называются B ^{+ * ** +1046 +1047 * дерева * * тысяча сорок девять.}

Answer 2

Возможно, вам стоит взглянуть на Ubiquitous B-Tree от Comer (ACM Computing Surveys, 1979).

Comer пишет там что-то о B * Tree (в разделе B-Tree и его вариантах). И в этом разделе он также цитирует еще несколько статей на эту тему. Это должно помочь вам провести дальнейшие расследования самостоятельно :)! (Я не твой исследователь;))

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

Относительно наличия только одного B-дерева. На самом деле, у вас есть это. Другие, такие как B + Tree, Prefix B + Tree и т. Д., Являются лишь вариантами стандартного B-Tree. Достаточно взглянуть на бумагу Вездесущий B-Tree.