Руководство по созданию эффективных запросов

Почему так часто используются B-деревья?
Из информатики мы знаем, что ни один алгоритм поиска не может найти 
индексный ключ среди 
N
различных ключей быстрее, чем за время 
log
N
(вы-
раженное в инструкциях процессора). Такая производительность достигает-
ся с помощью двоичного поиска по упорядоченному списку или с помощью 
двоичных деревьев. Однако стоимость обновлений (например, вставки но-
вых ключей) может быть очень высока как для упорядоченных списков, так 
и для двоичных деревьев: вставка одной записи может привести к полной 
реструктуризации. Это делает обе структуры непригодными для хранения 
на диске.
Напротив, B-деревья можно изменять без значительных накладных рас-
ходов. Когда вы вставляете запись, реструктуризация ограничена одним 
блоком. Если емкость блока превышена, то он расщепляется на два блока, 
и обновление распространяется на верхние уровни. Даже в худшем случае 
количество измененных блоков не будет превышать глубины дерева.

---

50

Еще больше теории: алгоритмы
Чтобы оценить стоимость поиска в B-дереве, нужно вычислить его глубину. 
Если каждый блок содержит 
f
указателей, то количество блоков на каждом 
уровне в 
f
раз больше, чем в предыдущем. Следовательно, глубина дерева, 
содержащего 
N
записей, равна 
log
N
/
log
f
. Эта формула дает количество об-
ращений к диску, необходимое для поиска по одному ключу. Количество ин-
струкций процессора для каждого блока ограничено, и обычно внутри блока 
используется двоичный поиск. Следовательно, стоимость ресурсов процес-
сора лишь ненамного хуже теоретически возможного лучшего варианта. Раз-
мер блока в PostgreSQL составляет 8 Кбайт. В такой блок помещаются десятки 
индексных записей; следовательно, индекс с шестью-семью уровнями может 
вместить миллиарды записей.
В PostgreSQL индекс на основе B-дерева можно создать для любого поряд-
кового типа данных; то есть такого, что из любых двух различных значений 
этого типа одно значение меньше другого. В эту категорию входят и поль-
зовательские типы.
Битовые карты
Битовая карта – это вспомогательная структура данных, которая использу-
ется внутри PostgreSQL с разными целями. Битовые карты можно рассмат-
ривать как своего рода индекс: они созданы для облегчения доступа к дру-
гим структурам данных, содержащим несколько блоков. Обычно битовые 
карты используются для компактного представления свойств табличных 
данных.
Чаще всего битовая карта содержит по одному биту для каждого блока 
(8192 байта). Значение бита равно 1, если блок обладает нужным свойством, 
и 0, если нет. На рис. 3.7 показано, как битовые карты используются для до-
ступа к данным по нескольким индексам.