Где кластерный индекс хранит данные строки для ключей на промежуточных уровнях?

Question

Пожалуйста, помогите мне понять, что я чувствую несоответствие между двумя фактами:

1. хранит данные SQL Server в структуре B-Tree
2. только листовые узлы содержат фактические данные таблицы, в то время как промежуточные хранить только ключи и указатели на детей

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

В приведенном выше примере (image credit) четко указана строка с идентификатором = 7. Но где данные строки (несетевые столбцы) для этого идентификатора, если они не могут быть в корневом узле примера, и нет 7 в листовых узлах?

Очевидно, что для этого есть нечто большее, чем «индексы B-Trees», и я был бы признателен за понимание.

Answer 1

Я думаю, что хороший обзор эта статья:

https://www.simple-talk.com/sql/database-administration/sql-server-storage-internals-101/

См часть индексов. Там показано, что узлы, как 7 или 16 также имеет свои листья Кроме того, я настоятельно рекомендую книгу:

SQL Server 2012 внутрикорпусных по Кален Делани

https://www.amazon.com/Microsoft-Server-Internals-Developer-Reference/dp/0735658560

Answer 2

При построении индекса B-дерева, он начинается с уровня листа - данные сортируются и записываются на страницы данных и создается созданный двойной список.

Наименьшее значение ключа (NULL с первой страницы) взято с каждой страницы и используется для создания индексных страниц для следующего уровня индекса, поэтому каждая строка на индексной странице содержит идентификатор страницы ниже и наименьшее значение ключа от него. Он делает то же самое, беря наименьшее значение ключа с каждой индексной страницы, чтобы создать следующий уровень.

Это продолжается до тех пор, пока все не войдет в одну страницу - это корень.

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

На рисунке выше, считая, что это только три страницы уровня листа и корень, корень должен содержать (pageID:1 Key:NULL), (pageID:2 Key:9) и (pageID:3 Key:18).

Answer 3

Эта диаграмма предназначена для B-дерева, но с технической точки зрения SQL Server использует структуру дерева B +. Прокрутите вниз немного в этом Wiki article, и вы найдете

В дереве B + копии ключей хранятся во внутренних узлах; ключи и записи хранятся в листьях; кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа (Comer 1979, стр. 129).

Таким образом, внутренние узлы будут иметь только копию ключей, и будут дублироваться в листьях (где, в случае кластерного индекса, фактические данные, которые проводятся, а).

Вы можете найти более подробную информацию here. Вы заметите в разделе комментариев пару других людей, которые отмечают, что SQL Server использует дерево B +.

Answer 4

(Пожалуйста, простите мои Word, навыки рисования)

Хотя ваш образ действительно представляет B-Tree, фактический SQL Server имеет несколько иную реализацию, в частности В + дерева. Я попытаюсь объяснить, используя визуальные эффекты, а также, принимая схему ниже в качестве примера:

Как показано на схеме, ключи не существуют только в одном узле (в данном случае корень), но они копируются и распределяются между дочерними узлами вплоть до узлов листа. (В этом случае дерево имеет только 2 уровня, корневой и листовой уровни).

Таким образом, при выполнении запроса для ключа (Adams, Joe) ключ будет искать в B-Tree в соответствии с правилами, указанными в вопросе (меньшие клавиши слева, большие клавиши справа).

Это будет продолжаться до тех пор, пока не будет достигнут узел LEAF.

На данный момент есть 2 различия, в частности, для SQL Server:

• некластеризованный индекс (представлен на диаграмме выше):

  • содержит/столбец PAGE_ID ROW_ID который указывает на страницу данных, где существует эта строка
  • механизм базы данных извлекает эту страницу и просматривает ее для ROW_ID

• кластерный индекс:

  • содержит всю страницу данных на уровне листьев
  • база данных не требуется, чтобы получить страницу, так как она уже на уровне листьев, а просто делает поиск ключа внутри страницы