Как используется последовательный переход между промежуточными листьями кластерного индекса?

Question

Промежуточные листья кластеризованного индекса связаны последовательно (следующий, предыдущий) для более быстрого доступа (между промежуточными узлами) [1], [2] и т. Д .:

Как этот доступ используется?
Зачем это нужно?

[1]
Структуры кластерного индекса
http://msdn.microsoft.com/en-us/library/ms177443.aspx
[2]
Кластерные таблицы и таблицы кучи
http://www.mssqltips.com/tip.asp?tip=1254

Обновление: Дополнительный вопрос к ответчикам:

• Каковы полезные случаи использования Internals Viewer для SQL Server, чтобы убедить меня его использовать?

Answer 1

Во-первых, как указывалось в PerfomanceDBA, для понимания внутренних особенностей SQL Server лучше использовать документацию и терминологию Sybase.

Во-вторых, хорошее объяснение, где, почему и как последовательное прохождение промежуточного уровня объясняется в [1]:

• "Чтение впереди при сканировании по заказу ключа

  При сканировании с упорядочением по ключам механизм использует информацию, хранящуюся на промежуточных страницах индекса на 1 уровень выше конечного уровня, для составления графика последовательного опережающего считывания для страниц, которые содержат найденные ключи. Если запрос сделан, например, для всех ключей от 1 до 100, механизм сначала прочитает страницу индекса над листовой страницей для ключа 1 (на пути к переходу на листовую страницу); однако вместо простого чтения каждой конечной страницы последовательно от страницы 1 до страницы 100 механизм сканирует страницу промежуточного уровня и создает список конечных страниц, которые необходимо прочитать, чтобы получить страницы со 1 по 100, а затем планирует все операции чтения в ключе. order - кроме того, механизм распознает, являются ли страницы смежными, и выполняет одно чтение для извлечения смежных страниц за одну операцию, а не за несколько меньших операций. Аналогичный тип операции используется для предварительной выборки данных из базового кластера или кучи при сканировании через некластеризованный индекс - поскольку листовые строки некластеризованного индекса содержат указатели на строки данных в структуре кластера / кучи, По мере того, как механизм хранения считывает лист некластеризованного индекса, он также начинает планировать асинхронные чтения для соответствующих строк данных, указатели которых уже были получены. Это позволяет ядру эффективно извлекать данные из базового кластера / кучи до завершения сканирования некластеризованного индекса.

  Навигация для упреждающего чтения при упорядоченном сканировании будет выглядеть примерно так:

«

[1]
Чед Бойд
MSSQLTips - Блог о SQL Server
Станция фрагментации - остановка № 1 - Основы хранения и методы доступа http://blogs.mssqltips.com/blogs/chadboyd/archive/2007/11/12/fragmentation-station-stop-1-storage-basics-and-access-methods.aspx

Answer 2

Диаграмма в вашем вопросе совершенно точно отражает индексы в Microsoft SQL Server.

Для решения некоторых аспектов ответа PerformanceDBA, который я считаю неверным или неадекватно объясненным.

«Кластерный индекс (а не некластеризованные индексы) может использоваться для запросов диапазона»

Неверно: некластеризованные индексы могут отлично использоваться для запросов диапазона, если неКластерный индекс охватывает.

«CI намного быстрее, чем NCI; они гораздо более улучшены, потому что NCI зависит от них» *

Структура дерева B кластеризованногоИндекс не отличается от некластеризованного индекса.КИ не улучшены или как-то имеют другую и превосходную структуру.Если что-то NCI немного улучшено в том, что они не всегда имеют NULL_BITMAP и байт «Status Bits B» и, таким образом, могут быть немного более компактными.

«Промежуточные уровни имеют один указательна страницу на следующем уровне (не несколько указателей) ... Нет указателей на строки (на промежуточном ИЛИ листовом уровне). "

USE tempdb

IF OBJECT_ID('testing') IS NULL
BEGIN
    CREATE TABLE testing
    (
    a INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
    b INT NOT NULL,
    c CHAR(4000) NOT NULL DEFAULT REPLICATE('c',4000),
    d CHAR(4000) NOT NULL DEFAULT REPLICATE('d',4000)
    )

    CREATE UNIQUE NONCLUSTERED  INDEX ix ON testing (b) INCLUDE (d)

    INSERT INTO testing (b)
    SELECT TOP 3000 ROW_NUMBER() OVER (ORDER BY (SELECT 0))
    FROM sys.all_columns s1, sys.all_columns s2
END

IF OBJECT_ID('index_pages') IS NULL
BEGIN
CREATE TABLE index_pages
(
PageFID TINYINT,
PagePID INT,
IAMFID TINYINT,
IAMPID INT,
ObjectID INT,
IndexID TINYINT,
PartitionNumber TINYINT,
PartitionID BIGINT,
iam_chain_type VARCHAR(30),
PageType TINYINT,
IndexLevel TINYINT,
NextPageFID TINYINT,
NextPagePID INT,
PrevPageFID TINYINT,
PrevPagePID INT,
PRIMARY KEY (PageFID, PagePID)
) 
END
ELSE
TRUNCATE TABLE index_pages

INSERT INTO index_pages
EXEC('DBCC IND(tempdb, testing, 2)') 

SELECT * 
FROM index_pages 
ORDER BY IndexLevel DESC

Вы увидите, что первый уровень(промежуточный уровень) страницы имеют горизонтальные указатели, обозначенные столбцами NextPagePID и PrevPagePID.В дополнение к этим указателям уровня страницы каждая запись индекса имеет указатель на страницу следующего уровня вниз, как правильно указано на диаграмме.

Чтобы увидеть это, выберите один из PagePID, принадлежащих странице первого уровня, и посмотрите на эту страницу в Internals Viewer для SQL Server .Вы увидите (как показано ниже), что каждая индексная запись имеет свой собственный указатель вниз страницы.

В конкретной отдельной записи, выбранной на снимке экрана ниже, видно, что он показывает, что первая запись на листовой странице 1:186 будет иметь значение ключа 13 или более позднюю.

Answer 3

Кластерный индекс (а не некластеризованные индексы) можно использовать для запросов диапазона. Ты знаешь что это? Горизонтальный обход B-дерева повышает скорость навигации по CI при определении квалифицированных строк во время запросов диапазона.

В более общем смысле, если кэш сервера слишком мал и страницы CI выгружаются, когда любой запрос (не только запросы диапазона) должен получить следующую страницу при переходе вниз или вбок, через CI, он может получить страницу с одним доступом к диску, потому что страницы связаны указателем; то есть. это позволяет избежать перехода на один уровень вверх, чтобы найти следующую страницу). Просто один из многих причин, по которым CI намного быстрее, чем NCI; они гораздо лучше, потому что от них зависит NCI (ваш второй вопрос сегодня).

Диаграмма содержит ошибки (содержит ложную информацию), или, если быть более точным, это описательная, нетехническая диаграмма от нетехнической корпорации:

1. Промежуточные уровни имеют один указатель на страницу следующего уровня (не несколько указателей).

2. Конечный уровень - это строка данных. Нет указателей на строки (на промежуточном ИЛИ листовом уровне).

3. Страницы указателя не похожи на страницы текста и изображений. Каждая страница индекса содержит сотни записей индекса B-Tree.

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

Существует причина, по которой технические специалисты рисуют и используют технические чертежи: среди прочего, это позволяет избежать недоразумений и путаницы. Никаких вопросов по Диаграмме, которую я сделал для вас ?

Ответ на пост Мартина Смита

а. Я: Кластерный индекс (а не некластеризованные индексы) можно использовать для запросов диапазона

MS: Неправильно: некластеризованные индексы могут отлично использоваться для запросов диапазона, если охватывает некластеризованный индекс.

Похоже, вы понимаете закрытый запрос, но не понимаете запрос диапазона. Пожалуйста, прочтите это. К сожалению, он называется «запрос», но на самом деле это техника производительности, которую предоставляют все поставщики SQL. Допустим, у вас есть настоящая реляционная таблица, что означает составной ключ, например. PK счета (CustomerId, InvoiceNo) [не InvoiceId]. Затем запрос, такой как:

SELECT * FROM Invoice WHERE CustomerId = @CustomerId

будет перемещаться по B-дереву ClusteredIndex один раз , чтобы найти первый счет-фактуру для CustomerId. Затем он будет следовать PageChain из LeafLevel (строки данных), чтобы получить второй и последующий счет-фактуру для CustomerId. Больше нет необходимости использовать B-Tree для запроса. Запрос диапазона заканчивается, когда встречается первый Счет с CustomerId> 1.

Это только возможно с ClusteredIndex, где B-дерево объединено с данными в единой физической структуре.

Это физически невозможно с NonClusteredIndex-plus-Data (который является кучей или ClusteredIndex). Вот почему Range Queries не может поддерживаться для NCI. Даже если у вас был NCI с (CustomerId, InvoiceNo), строки данных не будут в этом порядке; они будут в хронологическом порядке в куче; поэтому запрос, использующий этот NCI, извлечет запись по одной строке на NCI.

б. Я: CI намного быстрее, чем NCI; они намного более улучшены, потому что NCI зависит от них

MS: Структура дерева B кластеризованного индекса ничем не отличается от некластеризованного индекса. CI не улучшены или имеют какую-то другую и превосходную структуру ...

Там нет споров. Вы просто неправильно меня поняли, о скорость , я говорил о таблице в целом (NonClusteredIndices не может существовать самостоятельно). Позвольте мне уточнить: учитывая тот же ключ, ClusteredIndex (который включает в себя данные) всегда намного быстрее, чем NonClusteredIndex-plus-Heap. Навигация, поддержка, создание, удаление из единой структуры хранения данных (CI), очевидно, намного быстрее, чем выполнение той же операции с двумя структурами хранения данных (NCI + Heap).

Физически невозможно сделать две DS быстрее, чем одну DS (при условии, с одним и тем же ключом).

с. Не стоит ответа. Похоже, вы не понимаете, что мои комментарии относятся к неправильным диаграммам. Другими словами, ваши комментарии (и доказательства) также совершенно правильны.