Щільна і неплотная індексація

Як вже було кілька разів зазначено, основне призначення будь-якого індексу полягає в підвищенні швидкодії вибірки, а саме, індекс призначений для зменшення кількості дискових операцій введення-виведення, необхідних для вибірки деякої зазначеної запису По суті, це завдання виконується за допомогою покажчиків, а аж до цього моменту передбачалося, що всі такі покажчики являють собою покажчики на запису (тобто ідентифікатори записів) Але фактично для досягнення зазначеної мети досить, щоб ці покажчики представляли собою просто покажчики на сторінки (тобто номери сторінок) Вірно, що після цього для пошуку необхідної записи на зазначеній сторінці система повинна виконати деяку додаткову роботу, яка полягає в тому, що в оперативній памяті здійснюється пошук даних на сторінці, але кількість операцій введення-виведення залишається незмінним

Примітка Насправді, наведена вище аналогія з предметним покажчиком книги являє собою приклад індексу, в якому покажчики є покажчиками на сторінки, а не покажчиками на записи (Під чим маються на увазі рядки або слова)

Розглянемо цю ідею більш докладно Нагадаємо, що будь-який конкретний файл має єдину

“Фізичну послідовність, представлену у вигляді комбінації, по-перше, послідовності записів на кожній сторінці і, по-друге, послідовності сторінок в містить цей файл наборі сторінок Припустимо, що зберігання файлу постачальників на диску організовано таким чином, що його фізична послідовність відповідає логічній послідовності, яка визначена за допомогою значень деякого поля, скажімо, поля номерів постачальників Іншими словами, припустимо, що файл постачальників кластеризувати по цьому полю (див опис внутріфайловой кластеризації в кінці розділу Г2) Припустимо також, що для цього поля потрібно індекс У такому випадку немає необхідності, щоб цей індекс містив окремий елемент для кожного запису в індексованих файлі (тобто в даному прикладі для кожного запису у файлі постачальників) потрібно лише передбачити для кожної сторінки по одному елементу, в якому вказаний максимальний номер постачальника на цій сторінці і відповідний номер сторінки, як показано на рис Г12 (тут для спрощення передбачається, що кожна конкретна сторінка може зберігати не більше двох записів постачальників)

Як приклад розглянемо, які дії повинні бути виконані для вибірки даних про постачальника S3 з використанням цього індексу Спочатку система повинна просканувати індекс, відшукуючи перший запис з номером постачальника, більшим чи рівним S3 Система знаходить елемент індексу для постачальника S4, який вказує (скажімо) на сторінку р Потім виконується вибірка сторінки р і перегляд її в оперативній памяті для пошуку необхідної запису (яка в даному прикладі, безумовно, буде виявлена ​​дуже швидко)

Рис Г 12 Приклад нещільного індексу

Індекс, подібний до наведеного на рис Г12, прийнято називати нещільним- nondense (або іноді розрідженим – Sparse), оскільки він не містить по одному елементу для кожного запису індексованого файлу (На відміну від цього, всі індекси, що розглядаються в цьому додатку, до цього моменту були щільними – Dense) Одна з переваг нещільного індексу полягає в тому, що він займає менше місця порівняно з відповідним щільним індексом, з тієї очевидної причини, що він містить менше елементів В результаті перегляд цього індексу також, швидше за все, відбувається швидше Недоліком такого індексу може виявитися те, що при його використанні більше немає можливості проводити перевірки на наявність даних із застосуванням лише одного індексу (див коротке зауваження з приводу виконання перевірок на наявність даних в підрозділі Способи використання індексів вище в цьому розділі)

Взагалі кажучи, слід зазначити, що будь-який конкретний файл може мати не більше однієї нещільного індексу, оскільки такий індекс заснований на (унікальному) фізичному впорядкування розглянутого файлу Всі інші індекси обовязково повинні бути щільними

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*