Индексы на базе В*-деревьев
Индексы по реверсированному ключу
жүктеу/скачать 239.92 Kb.
|
Индексы по реверсированному ключуКак следует из названия, в индексе по реверсированному ключу порядок байтов в хранимом ключе меняется на обратный. Если в строке хранится значение " ABC D" , то в ключе индекса по реверсированному ключу окажется значение " D CBA ". Чтобы понять, зачем это нужно, вспомним еще раз, как устроено стандартное В*-дерево. Важнее всего тот факт, что глубина В*-дерева определяется количеством записей в листовых узлах. Чем больше глубина дерева, тем больше в нем промежуточных уровней и тем больше операций ввода/вывода требуется для доступа к нужному листовому узлу. На рис. 4.1 мы видим приличный индекс по строковому столбцу. Он сбалансирован, то есть записи равномерно распределены по всем листовым узлам. Однако индексы не всегда устроены так замечательно. Монотонно возрастающие значения, например последовательные порядковые номера или увеличивающиеся даты, всегда добавляются справой стороны индекса. Кроме того, любые удаления из индекса имеют тенденцию смещаться к левому краю по мере удаления старых строк. Со временем В*-дерево становится несбалансированным, листовые узлы с левой стороны заполнены меньше, чем с правой. Из-за несбалансированного роста мы получаем излишне глубокое В*-дерево, в котором новые - большие - значения группируются справа, а левая часть оказывается разреженной. Все сказанное относится и к автоматически уменьшающимся значениям, только в этом случае более плотно заполненной оказывается левая часть. Эту проблему можно решить, периодически удаляя и заново создавая индекс. Но есть и другое решение - воспользоваться индексом по реверсированному ключу, изменив порядок байтов в значении на обратный. В результате индексные записи более равномерно распределяются по листовым узлам. Например, вместо того чтобы добавлять значения 234, 235 и 236 в правую часть индекса, мы преобразуем их в 432, 532 и 632 в момент записи и восстановим исходные значения в момент чтения. Такие значения распределены по листовым узлам более равномерно. В итоге применение индекса по реверсированному ключу позволяет исправить дисбаланс, вызванный добавлением монотонно возрастающих значений в стандартное В*- дерево. Дополнительную информацию об индексах по реверсированному ключу и условиях их применения вы найдете в документации Oracle. жүктеу/скачать 239.92 Kb. Достарыңызбен бөлісу:
|