Если я выполняю операцию поиска в памяти (ОЗУ) с деревьями b, то было бы лучше с точки зрения кеширования или некоторых других эффектов по сравнению с бинарными деревьями?
То, что я знаю,
binary search tress---O(log n)
btrees ---------------O(c log n)
в разных блогах было много обсуждений.
Алгоритмическая сложность такая же, поскольку O (log b n) = O (c log n) = O (log n), но постоянные факторы сильно отличаются.
B-деревья были разработаны для жестких дисков пластин, которые имеют огромное время доступа (перемещение головы в нужное положение), после чего считывается весь физический сектор. Создание узлов B-дерева, таких как сектор, минимизирует количество времени доступа и максимизирует полезные данные из каждой операции чтения.
Но если вы работаете из памяти (или SSD), у вас есть незначительное время доступа, поэтому лучше сравнить количество доступных слов.
Например, давайте планируем структуру данных для хранения 2 20 ключей по 1 слову каждый, в общей сложности 4MiB необработанных данных на 32-битной машине.
"B-tree" B-tree, сделанный для современных жестких дисков, будет иметь 4kiB-узлы, которые могут содержать до 512 ключей и указателей (более или менее). Глубина 2 с 100% заполнением имеет 2 ключа 18 поэтому нам нужна глубина 3. Как будет выглядеть средний поиск? В среднем ему нужно будет прочитать 3/8 (половина среднего заполнения 3/4) каждого node на своем пути, от корня до упора = 4608 слов.
Двоичное дерево поиска будет содержать 2 20 узлов, каждый из которых содержит один ключ и два указателя (3 слова). Глубина будет 20. Средний поиск должен будет прочитать ключ и один из указателей из каждого node по его пути, от корня до упора вниз = 40 слов.
Кэширование памяти может облегчить разницу, но не может отменить эти числа.
С другой стороны, только B-деревья с памятью с гораздо более ограниченным коэффициентом ветвления работают лучше, чем бинарные деревья на практике.
32 ключа на node в частности, похоже, являются приятным местом для современных архитектур, как 32-, так и 64-разрядных. Многие новые языки и библиотеки используют 32-клавишные B-деревья в качестве встроенной структуры данных, наряду с хэш-таблицами и массивами или в качестве замены для них. Это использование было направлено Clojure и другими функциональными языками, но впоследствии было занято более основными языками, такими как Javascript, с недавним фокусом на неизменяемых структурах данных (например, Immutable.js)
Этот результат может быть вызван тем, что, хотя слова, к которым обращается алгоритм B-дерева, больше, чем слова бинарного дерева, количество промахов в кеше (операции чтения, которые заставляют CPU останавливаться и ждать основная ОЗУ) может быть ниже, чем в двоичном дереве, если архитектура кэширования может извлекать фрагменты ОЗУ, которые содержат всего B-дерево node за раз.
Здесь мы снова, оптимизация такая же, как для дискового массива, где мы используем B-деревья с узлами размером с физический сектор, чтобы минимизировать время доступа. В этом случае мы используем B-дерево с целыми узлами, как операция чтения, выполняемая кешем уровня 3 с ОЗУ, чтобы минимизировать промахи в кэше.
B-деревья отличаются от бинарных деревьев тем, что ключи и указатели кластеризованы в памяти, поэтому вы получаете несколько лучшее поведение кэша как на диске, так и в памяти. Тем не менее, нет разницы в условиях асимптотики (большой-O).