Блог

Если я реализую операцию поиска в памяти (RAM) с b-деревьями, то будет ли это лучше с точки зрения кэширования или некоторых других эффектов по сравнению с двоичными деревьями?

Что я знаю, так это-

 binary search tress---O(log n)
btrees ---------------O(c log n)
  

было много дискуссий по этому поводу в различных блогах.

Алгоритмическая сложность та же, поскольку O (log_b n) = O (c log n) = O (log n) но постоянные коэффициенты, которые скрыты в нотации big-O, могут заметно различаться в зависимости от реализации и аппаратного обеспечения.

B-деревья были разработаны для жестких дисков platter, которые имеют большое время доступа (перемещение головки в нужное положение), после чего считывается весь физический сектор. Создание узлов B-дерева размером с сектор сводит к минимуму количество обращений и максимизирует полезные данные при каждой операции чтения.

Но если вы работаете с нехваткой памяти, у вас незначительное время доступа, поэтому лучшее сравнение — подсчитать количество отдельных слов, к которым обращается ваш алгоритм.

Например, давайте спланируем структуру данных для хранения 2²⁰ ключей по 1 слову каждый, в общей сложности 4 МБ необработанных данных на 32-разрядной машине.

Бинарное дерево поиска будет иметь 2²⁰ узлов, каждый из которых содержит один ключ и два указателя (3 слова). Глубина будет равна log₂(2²⁰) = 20. Средний поиск должен будет считывать ключ и один из указателей из каждого узла на своем пути, от корня до конца = 40 слов.

B-дерево, созданное для жестких дисков, будет иметь узлы размером 4 КБ. Каждый узел может храниться внутри в виде отсортированного массива пар ключей и указателей, от 256 до 512 из них. Как будет выглядеть средний поиск? Учитывая среднее заполнение на 3/4, каждый узел будет содержать 384 записи, и его внутренний двоичный поиск должен будет посещать в среднем ₂(384) = 5,95 ключа журнала. Средняя глубина будет составлять ₃₈₄ логарифма (2²⁰) = 2,33, поэтому для нашего поиска придется прочитать в среднем 2,33 раза по 5,95 ключа, или около 14 слов.

В случае B-дерева с низким коэффициентом разветвления (коэффициент ветвления), когда каждый узел содержит от 16 до 32 ключей, среднее заполнение составит 24 ключа, средняя глубина log₂₄(2²⁰) = 4,36, двоичный поиск в каждом узле произведет сравнения log₂ (24) = 4,58, а общий средний поиск должен будет содержать около 20 слов.

Имейте в виду, что последние две структуры данных достигают лучшего результата, чем двоичные деревья, потому что они оптимизируют операции чтения по сравнению с изменениями. Чтобы вставить ключ в одно из этих B-деревьев, вам пришлось бы переписать в среднем весь узел из 384 слов или 24 слов, если не более одного, в то время как в случае с двоичным деревом операции записи все равно потребовалось бы затронуть только до 40 слов.

(Ранее у меня это было неправильно. Спасибо @virco и @Groo за указание на мою ошибку в комментариях.)

В любом случае, кажется, что B-деревья только для памяти с низким разветвлением на практике работают лучше, чем бинарные деревья.

32 ключа на узел, в частности, кажутся оптимальным вариантом для современных архитектур, как 32-, так и 64-разрядных. Многие новые языки и библиотеки используют 32-ключевые B-деревья в качестве встроенной структуры данных, наряду с хэш-таблицами и массивами или в качестве замены им. Это использование было инициировано Clojure и другими функциональными языками, но впоследствии было подхвачено более распространенными языками, такими как Javascript, с недавним акцентом на неизменяемые структуры данных (например. Immutable.js )

Этот результат может быть объяснен не только подсчетом количества слов, считываемых из памяти, но и пропусками в кэше, которые являются операциями чтения, которые заставляют процессор зависать и ждать ОЗУ. Если архитектура кэширования может извлекать фрагменты оперативной памяти, содержащие целый узел B-дерева за раз, мы получаем ту же оптимизацию, которая успешно использовалась для массового хранилища на диске.

В случае оптимизированных для жесткого диска структур данных мы бы использовали B-деревья с узлами размером с сектор физического диска, чтобы минимизировать время доступа к диску. В этом случае мы используем B-деревья с узлами размером с операцию чтения, выполняемую кэшем уровня 3 в оперативной памяти, чтобы минимизировать промахи в кэше.

B-деревья отличаются от двоичных деревьев тем, что ключи и указатели кластеризованы в памяти, поэтому вы получаете несколько лучшее поведение кэша как на диске, так и в памяти. Однако в асимптотической (big-O) среде выполнения нет разницы.