Классика баз данных - статьи
Это сделало бы традиционный поиск
Это сделало бы традиционный поиск в среднем менее эффективным. С другой стороны, другие виды поиска могли бы поддерживаться более эффективно. В частности, в системе, обеспечивающей приблизительные ответы на запросы, корень такого дерева обеспечивал бы более качественный ответ, чем корень соответствующего B+-дерева. Кроме того, система может перейти в поступательный режим, продвигаясь по дереву обычным образом и обеспечивая последовательность ответов с постоянным улучшением качества, в конце концов достигая листов и окончательного, точного ответа.
Возвращаясь к точным ответам на запросы, заметим, что обычно индексы строятся в предположении, что все значения в диапазонах значений одинаково важны. Поэтому важно иметь сбалансированное дерево. Однако часто бывает так, что разные значения обладают разной важностью и разной частотой в ожидаемой рабочей нагрузке []. Если эта частота запросов или некоторый другой подобный параметр используется в соединении с развитыми гистограммными правилами разделения на бакеты, то могут генерироваться некоторые очень интересные деревья, обеспечивающие намного лучшую среднюю эффективность поиска, чем у B+-деревьев.
Из всего этого ясно, что взаимодействие между гистограммами и индексами предоставляет ряд благоприятных возможностей, но также выдвигает и несколько технических проблем, которые нуждаются в исследовании. Специальное внимание требуется изучению соотношения плюсов и минусов иерархических гистограмм, являющихся сбалансированными деревьями с разделением на бакеты одинаковой ширины, и несбалансированных иерархических гистограмм с более совершенным разделением на бакеты. Нельзя также исключать возможность некоторых абсолютно новых структур, которые обеспечивали бы еще лучшие средние характеристики, объединяя лучшие черты данных двух миров.
