Как организован многостолбцовый индекс b-дерева - PullRequest
Новая
       8

Как организован многостолбцовый индекс b-дерева

2 голосов
/ 15 сентября 2010

Я хочу лучше понять организацию индекса.Представьте, что у нас есть таблица с 2 столбцами: 

CREATE TABLE user( 
  name varchar(100)
 ,age int)

Мы хотели бы создать индекс: 

CREATE INDEX IDX_MultiColIdx on user(name,age)

Как будет выглядеть организация индекса B-Tree?

В случае одного столбца, скажем, age , организация понятна: каждый неконечный узел будет содержать набор целочисленных ключей, которые будут использоваться для поиска.Какие значения содержат узлы нашего IDX_MultiColIdx индекса B-Tree?

Ответы [ 2 ]

4 голосов
/ 15 сентября 2010

Какие значения содержат узлы нашего IDX_MultiColIdx Индекс B-Tree?

Значения name, age и указатель строки (RID / ROWID или кластерный ключ, в зависимости от организации таблицы), отсортированные лексикографически.

Как именно они будут храниться, зависит от типа данных и системы базы данных.

Обычно CHAR хранится справа от пробелов до его размера, тогда как VARCHAR добавляется с его длиной.

MyISAM и некоторые другие движки могут использовать сжатие клавиш : совпадающие части набора ключей сохраняются только один раз, а другие ключи хранят только разные части, например: 

Hamblin
Hamblin, California
Hamblin (surname)
Hambling Baronets
Hambly
Hambly Arena    
Hambly Arena Fire
Hambo
Hambo Lama Itigelov
Hambok
Hambone

будет храниться как: 

Hamblin
[7], California
[7] (surname)
[7]g Baronets
Hambly
[6] Arena   
[6] Arena Fire
Hambo
[5] Lama Itigelov
[5]k
[5]ne

, где [x] означает «взять начальные x символов от предыдущего ключа»

1 голос
/ 15 сентября 2010

Я предполагаю, что вы спрашиваете о реализации внутренней базы данных, потому что упоминаете «неконечные узлы».

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

Например, если индекс с последовательными ключами <'Очень длинныйстрока ', 314159> и <' Не та же строка ', 9348>, все, что должен представлять внутренний узел, - это разделение между теми теми ключами, которые могут быть представлены одним символом.Аналогичным образом, когда ключи, подлежащие разделению во внутреннем узле, имеют общий префикс, этот префикс необходимо сохранить только один раз, а точка, где они расходятся, представлена.

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

Хорошую справку по этому вопросу см. В разделе «Обработка транзакций: концепции и методы» Gray & Reuter и следуйте инструкциямссылки, если вы хотите более подробно.

...