Классика баз данных - статьи
Гистограммы и древовидные индексы
В нескольких работах признавался тот факт, что имеется тесная связь между приближенной статистикой, сохраняемой в базах данных, главным образом, гистограммами и индексами []. Если взглянуть на корень B+-дерева, то легко заметить, что появляющиеся в нем значения, по существу, разделяют атрибут, на котором построен индекс, на бакеты с соответствующими границами. Затем каждый бакет подразделяется на более мелкие бакеты узлами последующего уровня дерева. Можно представить, что рядом с каждым бакетом, специфицированным в узле, сохраняется соответствующая информация, так что узел преобразуется в гистограмму, а индекс целиком - в так называемую иерархическую гистограмму. Конечно, это может неблагоприятно повлиять на эффективность поиска в индексе, поскольку может уменьшить полустепень исхода узла (out-degree) и тем самым увеличить глубину дерева. Тем не менее, хотя эта идея работает против функциональности индекса, нельзя игнорировать ее достоинства, и этот подход даже внедрен в некоторых системах.
Мы полагаем, что иерархические гистограммы и вообще взаимодействие между аппроксимирующими структурами и индексами следует продолжать исследовать, поскольку, как показывает приводимый ниже анализ, несколько интересных проблем остаются неисследованными. Снова рассмотрим B+-дерево, узлы которого полностью заполнены. В этом случае корень дерева специфицирует разделение на бакеты домена атрибута, соответствующее гистограмме с одинаковой шириной, т.е. каждый бакет содержит примерно одинаковое число элементов. Аналогично, каждый узел дерева специфицирует разделение на бакеты с одинаковой шириной диапазона значений, к которым ведет этот узел.
Основной проблемой превращения B+-деревьев в гистограммы с одинаковой шириной является то, что эти гистограммы далеки от оптимальных при оценке селективности []. Гораздо эффективнее гистограммы классов v-optimal и maxdiff. Какие виды индексов следует применять, чтобы каждый узел представлял разделение на бакеты в соответствии с одним из этих правил? Ясно, что деревья были бы несбалансированными.
