3.2. Индексиране
Както беше отбелязано по-горе, указването на ключ за таблица означава автоматично сортиране на записи, гарантиране, че няма дублиращи се стойности в ключовите полета на записите и ускоряване на търсенето в таблицата. За реализиране на тези функции в СУБД се използваиндексиране.
Терминът "индекс" е тясно свързан с понятието "ключ", въпреки че има известна разлика между тях.
индекссе разбира като средство заускоряване наоперацията за намиране на записи в таблица и, следователно, други операции, които използват търсене: извличане, модифициране, сортиране и т.н. Таблица, за която се използва индекс, се наричаиндексирана.
Възможностите за решаване на проблема с организирането на физическия достъп до информация зависят главно от следните фактори:
типа на съдържанието в полето за ключ за запис на индексния файл;
вида на връзките (указателите), използвани за запис на основната таблица;
метод за намиране на желаните записи.
Включовото поле на индексния файлможете да съхранявате стойностите на ключовите полета на индексираната таблица или ключово сгъване (т.нар. хеш код). Предимството на съхраняването на хеш код вместо стойност е, че дължината на конволюцията, независимо от дължината на първоначалната стойност на ключовото поле, винаги има някаква постоянна и доста малка стойност (например 4 байта), което значително намалява времето за операции за търсене. Недостатъкът на хеширането е необходимостта от извършване на операцията за навиване (изисква определено време), както и борбата срещу възникването на сблъсъци (конволюцията на различни стойности може да даде един и същ хеш код).
На практика най-често се използватдва метода на търсене:последователен и двоичен (базиран на разделяне на интервала на търсене наполовина).
Ние илюстрираме организацията на индексиращите таблици с две схеми:едностепенни и двустепенни. В този случай ще приемем редица допускания, които обикновено се изпълняват в съвременните изчислителни системи. Нека операционната система поддържа директно организиране на данни на магнитни дискове, основните таблици и индексните файлове се съхраняват в отделни файлове. Информацията за файла се съхранява като набор от блокове с фиксиран размер, като например цяло число клъстери.
Ориз. 3.3. Схема за индексиране на едно ниво
Във всеки блок записите са подредени във възходящ ред на стойността на ключа или конволюцията. Основният ключ на всеки блок е ключът на последния му запис.
Ако хеш-кодовете на ключовите полета на индексираната таблица се съхраняват в индексния файл, тогава алгоритъмът за търсене на желания запис (с посочения ключ) в таблицата включва следните три етапа.
Формиране на конволюция на стойността на ключовото поле на необходимия запис.
Потърсете в индексния файл запис на блок, чиято стойност на първото поле е по-голяма от полученото сгъване (това гарантира, че желаното сгъване е намерено в този блок).
Схема на две нивав някои случаи се оказва по-рационална, при която ключовете (гънките) на записите са отделени от съдържанието на записите (фиг. 3.4).
Ориз. 3.4. Двустепенна схема на индексиране
В тази схема индексът на основната таблица е разпределен върху набор от файлове: един основен индексен файл и много файлове с ключови блокове.
На практика, за да създаде индекс за някаква таблица на база данни, потребителят определя поле на таблица, което изисква индексиране. Ключовите полета на таблицата в много СУБД обикновено се индексират автоматично. Индексните файлове, създадени върху ключовите полета на таблица, често се наричат основни индексни файлове.
Асоциирането на вторичен индекс с елементи от данни в базата данни може да се установи по различни начини. Един отедин от тях е използването на вторичен индекс като вход за получаване на първичен ключ, който след това се използва за търсене на необходимите записи с помощта на първичния индекс (фиг. 3.5).
Ориз. 3.5. Как да използвате вторични индекси
Някои СУБД, като Access, не разделят индексите на първични и вторични. В този случай се използват автоматично създадени индекси и индекси, дефинирани от потребителя за някое от неключовите полета.
Основната причина за ускоряване на различни операции върху индексирани таблици е, че по-голямата част от работата се извършва върху малки индексни файлове, а не върху самите таблици. Най-големият ефект от подобряването на работата с индексирани таблици се постига при големи таблици. Индексирането изисква малко допълнително дисково пространство и малко натоварване на процесора за промяна на индексите, докато работи. В общия случай индексите могат да се променят преди изпълнение на заявки към базата данни, след изпълнение на заявки към базата данни, чрез специални потребителски команди или извиквания на приложни програми.