Организация на индексите под формата на по-дървета

Изграждане на B-дърво е свързано с една проста идея за създаване на индекс на вече построена на индекса. Така например, в изграждането на индексирана последователно индекс площ файл от своя страна може да се разглежда като основен файл, на който може да се изгради в насипно състояние индекс, и така нататък, докато зоната на индекс не само ще представлява една единица.

В общия случай, може да бъде конструирана в дърво, всеки родител единица, която е свързана със същия брой на подчинените единици, равен на броя на индексни регистри настанени в родителското устройство. Броят на стъпки в този случай, за да намерите нито един запис на основната документация е идентична и равен на броя на нива в дървото.

Тези дървета са наречени балансиран (по пътя от корена на всяко листо и съща) По този начин, терминът произлиза от Б -tree английски баланс (баланс). Пример В-дървото е показано на Фигура 30.

С помощта на техника B-дърво сега вероятно ще бъде най-популярната подход към организацията на индексите в базата данни. От гледна точка на външния логическо представяне, B-дърво - балансиран, силно разклонени дърво в външна памет. Green дърво - дърво всеки възел собственост, за да се отнасят до голям брой деца възли. От гледна точка на физическата организация на. B-дървовидна структура е представена като multispisochnaya страници на външна памет, т.е., всеки възел на дървото съответства на един блок от външна памет (стр. Cm. P.7.3.2.). Вътрешни и листа страници обикновено имат различна структура.

Търсене в B-дърво - един пасаж от корена до листо в съответствие с дадена ключова стойност.

Обърнат файл (достъп от неосновните атрибути)

Посочените по-горе методи за достъп списък вписвания се извършват от основната стойност на ключа. Въпреки това, вида операция, за да получите известна представа критерий за подбор включва записи копия на стойностите на един или повече неключови атрибути (често се наричат ​​вторични и ключове) .Zametim, че съответната език SQL заявката включва клауза за къде.

А ключът към организиране на търсенето на стойности на не-ключов атрибут е инверсията на файла.

Обърнат на файла - файл, който се поддържа от гъста ценности вторични индекси за поле съдържа записи. Обърнатият файл се състои от индекса на няколко нива и набор от списъци за достъп на указатели. предоставяне на достъп до записи на данни.

показалеца на списък за достъп е физически последователно списък от указатели за записи, съдържащи идентични стойности на съответния атрибута.

В най-общ вариант на изпълнение, индекс на две нива. Организация диаграма на обърнато файл е показано на Фигура 31.

Частично обърнат файл обърнат върху селективна брой неключови атрибути.

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

Горният обсъдено изграждането на единични атрибути индекс (видове елементи от данни). Очевидно е, че е възможно да се използват композитни индекси. чиито елементи съответства на всеки тип съединени елементи.