Диапазон запросов с использованием B-деревьев и B + -деревьев
Я пишу программу для получения количества объектов в заданном диапазоне, и я использую структуру данных B-дерева для реализации моего решения, поскольку количество объектов не может поместиться в ОЗУ. Я сталкивался с несколькими статьями, в которых говорилось, что деревья B + намного превосходят деревья B для запросов диапазона и используются всеми основными реализациями баз данных. Мне не удалось понять, почему деревья B + превосходят деревья B, так как все данные хранятся на листе, и потребуется доступ к диску h (высота дерева), чтобы получить узел и выполнить запрос диапазона, пока в дереве B интервал может быть расположен на родительских узлах, и доступ к диску будет таким образом минимизирован. Кроме того, если у меня есть запрос, такой как возврат # объектов определенного ключа, тогда я смогу найти ключ, прежде чем спуститься полностью вниз к листьям, как в деревьях B +. Почему же тогда они говорят, что B + -дерева эффективны, чем B-деревья, для запросов диапазона? Если мне нужно написать программу для выполнения запросов диапазона, не должны ли деревья B быть правильной структурой данных? Заранее спасибо за ваши ответы!
Решение
Практические реализации дерева B и дерева B +, как правило, имеют узлы фиксированного размера в байтах, которые выбираются в соответствии с размером страницы архитектуры или другого устройства, такого как размер кластера на диске. Типичное значение будет 4096 байт.
Дерево B + может вместить намного больше ключей во внутренний узел, поскольку для данных записи не требуется места. Это дает большую разветвленность (меньшую высоту дерева) и лучшее использование кэша, поскольку данный набор страниц индекса (внутренних узлов) «покрывает» больше запросов, чем это было бы в случае B-дерева.
Второе преимущество B + деревьев заключается в том, что ключи во внутренних узлах нужны только для маршрутизации поисков до правого листа. Им нужно только отделить предметы слева от предметов справа, но они не должны соответствовать каким-либо фактическим ключам записи. Это означает, что они часто могут быть сокращены, и это также означает, что удаления не нужно распространять с листового слоя на слой индекса (т. Е. Как только вы удалили ключ из листа, все готово — не нужно удалить что-либо из внутренних узлов, кроме того, что происходит естественным образом во время перебалансировки).
Кроме того, в типичном дереве B + узлы листьев имеют указатели на своих левых и правых братьев и сестер. Это означает, что вы можете перебирать диапазон записей, обходя связанный список страниц, вместо того, чтобы использовать хитрую логику итерации, типичную для B-деревьев.
в дереве B интервал может быть расположен на родительских узлах, и таким образом доступ к диску будет минимизирован
Чтобы положить эту теорию в порядок, оцените, сколько всего ключей находится во внутренних узлах B-дерева и сколько всего ключей находится в конечных узлах. Это соотношение говорит о том, как часто поиск может быть остановлен рано, до того, как он полностью опустится до конечного уровня. Примечание. Ранний сценарий применим только к запросам, в которых точный случается, что ключ присутствует в дереве; в противном случае приличный до конечного уровня неизбежен.
Другие решения
Других решений пока нет …
detector