RID lookup - логический поиск

Question

Например, у нас есть таблица с кластеризованным индексом table1 (col1 int, col2 int, col3 int), кластеризованный индекс, определенный для col1, некластеризованный индекс, определенный для col2, мы пишем запрос - выберите * из таблицы1, где col2 = 'some value '- оптимизатор приходит к поиску некластеризованного индекса, захватывает заданную строку c и переходит к кластерному индексу, чтобы захватить остальные данные, которые не содержатся внутри некластеризованного индекса (в этом случае выполняется поиск ключа для захвата col3). По сути, поиск ключа - это поиск кластеризованного индекса на основе значения кластеризованного индекса, найденного в некластеризованном индексе на уровне листа.

Что происходит, когда у нас нет кластеризованного индекса в таблице, но у нас есть некластеризованный индекс? Я знаю, что он будет выполнять поиск RID, но как это логически работает? Значение кластеризованного индекса будет найдено с помощью поиска по b-дереву, поскольку у нас есть все строки в определенном порядке, но как это будет найдено в таблице кучи без какого-либо определенного порядка? Насколько я понимаю, когда мы нашли строку внутри некластеризованного индекса (у него есть ключ некластеризованного индекса + rowid), нам нужно отсканировать всю таблицу кучи, чтобы найти там этот идентификатор строки, потому что у нас там нет порядка и мы не можем перемещаться по этой строке, используя б-дерево, это правильно?

Answer 1

Это концептуальное объяснение. База данных хранит строки на страницах данных, которые в свою очередь хранят строки. rid напрямую определяет местоположение строки в терминах «физического» местоположения. На самом деле, страница данных является «логической» в том смысле, что она может находиться в памяти или на диске.

Базе данных не требуется go через пользовательские индексы, чтобы определить, где находится строка. Необходимо идентифицировать страницу, а затем смещение на странице. rid содержит информацию о том, какая страница и смещение. Таким образом, система управления страницами может напрямую найти нужную страницу из рида.

Нет необходимости сканировать что-либо, чтобы найти строку.

Тем не менее, есть вещи, которые база данных должна делать, например:

• Является ли страница данных в кеше страницы? Если нет, то go получите.
• Была ли изменена страница в памяти? Если нет, разрешено ли грязное чтение.
• Строка заблокирована?

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

Answer 2

Пример может помочь. Ниже создается куча и вставляется в нее пару строк

CREATE TABLE Demo(X CHAR(1));

INSERT INTO Demo VALUES ('A'), ('B');

Затем вы можете использовать следующую команду, чтобы увидеть RID

SELECT X,
       %%physloc%% as rid, 
       sys.fn_PhysLocFormatter(%%physloc%%) as formatted
FROM Demo

, который для меня возвращает

+---+--------------------+-----------+
| X |        rid         | formatted |
+---+--------------------+-----------+
| A | 0xE700000001000000 | (1:231:0) |
| B | 0xE700000001000100 | (1:231:1) |
+---+--------------------+-----------+

RID представляет собой 8-байтовое двоичное значение, которое представляет собой объединение трех компонентов. FileNumber:PageNumber:SlotNumber.

Каждый файл разделен на 8 КБ страниц с нумерацией, начинающейся с 0, поэтому вычислить смещение в файле для данного номера страницы несложно. Страница 231 - это 8-килобайтный раздел, начинающийся со смещения байта 1892352 в файле (231 * 8192).

Чтобы найти строку, принадлежащую RID 1:231:1, достаточно получить соответствующую страницу (1:231) из менеджер буфера (который будет читать его с дис c, если необходимо) и go во второй слот на странице (нумерация слотов начинается с 0).

Каждая страница данных имеет массив слотов в нижнем колонтитуле, задающий смещение строки для каждой строки на странице.