що дозволяє будувати різні процедури багатокрокового пошуку. [8]
2.2 Поняття індексу
Створення або впровадження СУБД обумовлено в першу чергу великими обсягами збережених і оброблюваних даних. Важливою операцією з даними є їх пошук. Сучасні СУБД використовують індекси для збережених даних, тобто проводиться їх індексація. Індекс - об'єкт бази даних, який створюється з метою підвищення продуктивності пошуку даних. Таблиці в базі даних можуть мати велику кількість рядків, які зберігаються в довільному порядку, і їх пошук за заданим критерієм шляхом послідовного перегляду таблиці рядок за рядком може займати багато часу. Індекс формується із значень одного або декількох стовпців таблиці і покажчиків на відповідні рядки таблиці і, таким чином, дозволяє шукати рядки, що задовольняють критерію пошуку. Прискорення роботи з використанням індексів досягається в першу чергу за рахунок того, що індекс має структуру, оптимізовану під пошук.
Існує два типи індексів: кластерні і некластерние. При наявності кластерного індексу рядка таблиці впорядковані за значенням ключа цього індексу. Якщо в таблиці немає кластерного індексу, таблиця називається купою. Некластерние індекс, створений для такої таблиці, містить тільки покажчики на записи таблиці. Кластерний індекс може бути тільки одним для кожної таблиці, але кожна таблиця може мати декілька різних некластерних індексів, кожний з яких визначає свій власний порядок проходження записів.
Індекси можуть бути реалізовані різними структурами. Найбільш частоупотребіми B *-дерева, B +-дерева, B-дерева і хеши.
Для ефективної роботи багатовимірними даними найпопулярнішими типами індексу є: GIST (Generalized Search Tree) і GIN (Generalized Inverted Index). GIN індекс, або узагальнений зворотний індекс - це структура даних, у якої ключем є лексема, а значенням - сортований список ідентифікаторів документів, які містять цю лексему. Так як у зворотному індексі використовується бінарне дерево для пошуку ключів, то він слабо залежить від їх кількості і тому добре шкалирующие. Цей індекс використовується практично всіма великими пошуковими машинами, однак його використання в базах даних для індексування змінюються документів ускладнене, оскільки будь-які зміни призводять до великої кількості оновлень індексу. Цей індекс найкраще підходить для незмінний колекцій документів. У теж час, GIST індекс є «прямим» індексом, тобто для кожного документа ставиться у відповідність битовая сигнатура, в якій міститься інформація про всі лексемах, які міститися в цьому документі, тому додавання нового докумен?? А призводить до додавання тільки однієї сигнатури.
Для визначення області застосування кожного з індексів необхідно знати їх основні відмінності:
· створення індексу - GIN вимагає в 3 рази більше часу ніж GIST;
· розмір індексу - GIN-індекс у 2-3 рази більше GIST-індексу;
· час пошуку - GIN-індекс у 3 рази швидше, ніж GIST-індекс;
· оновлення індексу - GIN-індекс оновлюється в 10 разів повільніше.
3. Пошукові системи
3.1 Поняття пошукової системи
Раніше неодноразово згадувалося поняття пошук...
