Индексные массивы. Нелинейные структуры

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

При организации индексов используют Б-деревья, которые представляют собой корневые сбалансированные сильно ветвистые деревья.

Каждая внутренняя вершина содержит информацию о n-1 различных последовательно возрастающих значениях индексируемого поля:

P_i X_i P_i+1 X_i+1... P_n-1 X_n-1 P_n

где X_i – i значение индексируемого поля,

P_i – указатель на вершину, содержащую значение индексируемого поля, меньшие или равные X_i

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

X_i P_i X_i+1 P_i+1... X_n P_n

где P_i – указатель страницу файла данных, содержащую строку (строки) со значением индексируемого поля, равным X_i

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

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