Достъп до данните по първичен ключ

2.4.1. Индексиране

Индексите са механизми за повишаване на скоростта на извличане на данните. Един индекс идентифицира колоните, които могат да бъдат използвани за извличане на редове от таблицата. Индексът осигурява средство за сканиране само на подмножество от редовете в таблицата и с това подобрява скоростта на достъп до данните

Повечето от съвременните СУБД автоматично дефинират индекси за първичния ключ на таблицата и за чуждите ключове

2.4.2. Хеширане

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

2.4.3. Метод на дихотомията

При търсене на запис със зададена стойност на ключа, индексът се разделя на две части и се проверява дали търсения ключ попада в първата или втората част. Тази част, в която попада търсеният ключ, отново се разделя на две части и се проверява в коя от тях попада търсения ключ. Това продължава до намиране на ключа или до установяване, че такъв ключ не съществува

2.4.4. Бинарни и балансирани дървета

Бинарни дървета

На всеки запис от таблицата с данни съответства един индексен запис. Първият индексен запис става коренов запис в структурата. Този корен повече не се изменя, а дървото расте надолу от корена. При постъпване на следващия индексен запис, неговият ключ се сравнява с корена. Ако новият запис има по-малък ключ от корена, извършва се преход наляво и надолу. Ако новият ключ е по-голям от корена, извършва се преход надясно и надолу. Следващият индексен запис се сравнява по същия начин с корена и след това със записите на по-ниските нива от корена.

Вижда се, че видът на бинарното дърво зависи от това кой ключ е коренов и в каква последователност постъпват останалите ключове в процеса на индексирането.

Балансирани дървета (Вдървета)

Дърво, чиито листа се намират на едно и също ниво, се нарича балансирано (листата му са равно отдалечени от корена). Коренът на Вдървото се изменя на всяка стъпка и дървото расте нагоре. Всеки индексен запис в структурата може да съдържа n адресни указателя и (n-1) ключа.

Алгоритъмът за формиране на балансираното дървоо се състои в това, че първоначално се запълва коренът, докато бъдат заети всички негови (n-1)