Различия между деревьями B и B + деревья
Я полагаю, что нашел ответ, включив всю таблицу сканирования в фактический CTE:
WITH RECURSIVE category_path (id, title, path) AS
(
SELECT category_id, category_default_label, category_default_label path FROM tbl_eav_categories WHERE parent_category_id IS NULL
UNION ALL
SELECT c.category_id, c.category_default_label, CONCAT(cp.path, ' [',c.parent_category_id, '] >> ', c.category_default_label) FROM category_path cp JOIN tbl_eav_categories c ON cp.id = c.parent_category_id
)
SELECT id,path FROM category_path
ORDER BY path;
6 ответов
Основным преимуществом деревьев B + перед деревьями B является то, что они позволяют упаковать больше указателей на другие узлы, удаляя указатели на данные, тем самым увеличивая разветвление и потенциально уменьшая глубину дерева.
Недостатком является то, что нет ранних выходов, когда вы могли найти совпадение во внутреннем узле. Но поскольку обе структуры данных имеют огромные разветвления, подавляющее большинство совпадений все равно будет на конечных узлах, что в среднем сделает дерево B + более эффективным.
Определите «намного быстрее». Асимптотически они примерно одинаковы. Различия заключаются в том, как они используют вторичное хранилище. Статьи в Википедии о B-деревьях и B + деревьях выглядят довольно достоверно.
Одно из возможных применений деревьев B + состоит в том, что оно подходит для ситуаций
где дерево вырастает настолько большим, что не помещается в доступные
объем памяти. Таким образом, обычно ожидается выполнение нескольких операций ввода-вывода.
Часто бывает, что дерево B + используется, даже если оно фактически вписывается в
память, и тогда ваш кеш-менеджер может держать ее там постоянно. Но
это частный случай, а не общий, и политика кеширования
отдельно от обслуживания дерева B + как такового.
Кроме того, в дереве B + листовые страницы связаны вместе в связанный список (или двусвязный список), который оптимизирует обход (для поиска по диапазонам, сортировки и т. д.). Таким образом, количество указателей равно функция конкретного используемого алгоритма.
B + Деревья намного проще и эффективнее для выполнения полного сканирования, например, посмотрите на каждую часть данных, индексируемую деревом, поскольку конечные узлы образуют связанный список. Чтобы выполнить полное сканирование с помощью B-дерева, вам необходимо выполнить полный обход дерева, чтобы найти все данные.
B-деревья, с другой стороны, могут быть быстрее, когда вы выполняете поиск (поиск определенного фрагмента данных по ключу), особенно когда дерево находится в ОЗУ или другом неблочном хранилище. Поскольку вы можете поднять часто используемые узлы в дереве, для получения данных требуется меньше сравнений.
B + Trees особенно хороши в блочном хранилище (например, на жестком диске). Имея это в виду, вы получаете несколько преимуществ, например (из верхней части моей головы):
высокий разветвитель / низкая глубина: это означает, что вам нужно получить меньше блоков для доступа к данным. с данными, смешанными с указателями, каждое чтение получает меньше указателей, поэтому вам нужно больше попыток получить данные
Простое и согласованное блочное хранилище: внутренний узел имеет N указателей, ничего больше, листовой узел имеет данные, ничего больше . это упрощает синтаксический анализ, отладку и даже реконструкцию.
высокая плотность ключей означает, что верхние узлы почти наверняка находятся в кэше, во многих случаях все внутренние узлы быстро кэшируются, поэтому на диск должен осуществляться только доступ к данным.
В дереве B+, так как во внутренних узлах хранятся только указатели, их размер значительно уменьшается по сравнению с внутренними узлами дерева B (в котором хранятся обе клавиши data+key). Таким образом, индексы B+-дерева могут быть извлечены из внешнего хранилища на одном прочитанном диске, обработанном для поиска местоположения цели. Если это было B-дерево, то для каждого процесса принятия решения требуется чтение диска. Надеюсь, я ясно выразился! :)