Алгоритмическая сложность такая же, поскольку O (log b n) = O (c log n) = O (log n), но постоянные коэффициенты, которые скрыты в нотации big-O, могутзаметно различаются, в зависимости от реализации и аппаратного обеспечения.
B-деревья были разработаны для жестких дисков с жесткими дисками, которые имеют большое время доступа (перемещение головки в нужное положение), после чего считывается весь физический сектор.Создание узлов B-дерева размером с сектор сводит к минимуму количество раз доступа и максимизирует полезные данные из каждой операции чтения.
Но если вы работаете без памяти, у вас незначительное время доступа, поэтомуЛучшее сравнение - подсчитать количество отдельных слов, к которым обращается ваш алгоритм.
Например, давайте спланируем структуру данных для хранения 2 20 ключей по 1 слову каждый, всего4 МБ необработанных данных на 32-битном компьютере.
Бинарное дерево поиска будет иметь 2 20 узлов, каждый из которых содержит один ключ и два указателя (3 слова).Глубина будет log 2 (2 20 ) = 20. Средний поиск должен будет прочитать ключ и один из указателей от каждого узла на его пути, от корня всепуть вниз = 40 слов .
B-дерево, созданное для жестких дисков, будет иметь узлы 4 КБ.Каждый узел может храниться внутри как отсортированный массив пар ключей и указателей, от 256 до 512 из них.Как будет выглядеть средний поиск?Учитывая среднее заполнение 3/4, каждый узел будет содержать 384 записи, и его внутренний двоичный поиск должен будет посещать в среднем log 2 (384) = 5,95 ключей.Средняя глубина будет log 384 (2 20 ) = 2,33, поэтому наш поиск должен будет прочитать в среднем 2,33 раза по 5,95 клавиш или около 14 слов .
В случае B-дерева с низким разветвлением (коэффициентом ветвления), когда каждый узел содержит от 16 до 32 клавиш, средняя заливка составит 24 ключа, средняя глубина записи 24 (2 20 ) = 4,36, двоичный поиск в каждом узле произведет сравнения журналов 2 (24) = 4,58, а общий средний поиск должен будет прочитать около 20 слов .
Имейте в виду, что последние две структуры данных достигают лучшего результата, чем двоичные деревья, потому что они оптимизируют операции чтения по сравнению с модификациями.Чтобы вставить ключ в одно из этих B-деревьев, вам нужно будет переписать в среднем весь узел из 384 слов или 24 слов, если не больше одного, в то время как в случае двоичного дерева операции записи все равно потребуетсякоснитесь до 40 слов.
(Ранее я ошибался. Спасибо @virco и @Groo за указание на мою ошибку в комментариях.)
В любомВ этом случае кажется, что B-деревья только с памятью с малым разветвлением на практике работают лучше, чем двоичные деревья .
32 ключей на узел, в частности, кажется хорошим местом длясовременные архитектуры, как 32-, так и 64-разрядные.Многие новые языки и библиотеки используют 32-клавишные B-деревья в качестве встроенной структуры данных , рядом или в качестве замены хеш-таблиц и массивов.Это использование было спровоцировано Clojure и другими функциональными языками, но впоследствии было принято более распространенными языками, такими как Javascript, с недавним акцентом на неизменяемые структуры данных (например, Immutable.js )
Этот результат может быть объяснен не только подсчетом количества слов, читаемых из памяти, но и отсутствием кэша, которые являются операциями чтения, которые приводят к остановке ЦП и ожиданию ОЗУ.Если архитектура кэширования может извлекать порции оперативной памяти, которые содержат весь узел B-дерева за один раз, мы получаем ту же оптимизацию, которая успешно использовалась для дискового запоминающего устройства.
В случае структур данных, оптимизированных для жесткого диска, мы бы использовали B-деревья с узлами размером с сектор физического диска, чтобы минимизировать время доступа к диску.В этом случае мы используем B-деревья с такими большими узлами, как операция чтения, выполняемая кэш-памятью уровня 3 для ОЗУ, чтобы минимизировать потери в кэш-памяти.