Питання Як працює індексування бази даних?


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

Для отримання інформації про запити щодо індексації поля перевірте Як індексувати стовпець бази даних.


1878
2017-08-04 10:07


походження


Ви можете перевірити - Як працює індексування бази даних? - Aniket Thakur


Відповіді:


Чому це потрібно?

Коли дані зберігаються на накопичувальних пристроях на диску, вони зберігаються як блоки даних. Ці блоки доступні в повному обсязі, роблячи їх операцією доступу до атомного диску. Дискові блоки структуровані так само, як і пов'язані списки; обидва містять розділ для даних, покажчик на розташування наступного вузла (або блоку), і обидві ці дані не потрібно зберігати одночасно.

Через те, що ряд записів можна відсортувати лише на одному полі, ми можемо стверджувати, що пошук у нерозсортованому полі вимагає лінійного пошуку, який вимагає N/2 блокування доступу (в середньому), де N це кількість блоків, які охоплює таблиця. Якщо це поле є полем, що не містить ключових слів (тобто не містить унікальних записів), то слід шукати весь цілий простір N блокування доступу.

У той час як з відсортованим полем може бути використаний бінарний пошук, який має log2 N блокування доступу. Крім того, оскільки дані сортуються за даними не ключового поля, в іншій частині таблиці не потрібно шукати повторювані значення, коли виявляється більш високе значення. Таким чином, підвищення продуктивності є суттєвим.

Що таке індексування?

Індексація - це спосіб сортування ряду записів на декількох полях. Створення індексу на полі в таблиці створює іншу структуру даних, яка містить значення поля, і покажчик на запис, до якого він відноситься. Потім ця структура індексу сортується, що дозволяє виконувати на ній двоичні пошуки.

Недоліком для індексації є те, що ці індекси вимагають додаткового місця на диску, оскільки індекси зберігаються разом у таблиці за допомогою двигуна MyISAM, цей файл може швидко досягти меж розміру основної файлової системи, якщо індексируються багато полів у тій самій таблиці .

Як це працює?

По-перше, давайте викладемо схему таблиці зразків;

Ім'я поля Тип даних Розмір на диску
id (Основний ключ) Непідписані INT 4 байти
firstName Char (50) 50 байт
lastName Char (50) 50 байт
EmailAddress Char (100) 100 байт

Примітка: замість varchar використовували символ, щоб забезпечити точний розмір на значення диска. Ця база даних зразків містить п'ять мільйонів рядків і неіндексована. Результати кількох запитів будуть тепер проаналізовані. Це запит з використанням ідентифікатор (поле сортованого ключа) і один, що використовує ім'я (не ключова неортована область).

Приклад 1 - сортовані проти несортованих полів

З огляду на нашу зразкову базу даних r = 5,000,000 записи фіксованого розміру, що дає довжину запису R = 204 байт, і вони зберігаються в таблиці за допомогою двигуна MyISAM, який використовує розмір блоку за замовчуванням B = 1,024байтів Коефіцієнт блокування таблиці буде bfr = (B/R) = 1024/204 = 5 записи на дисковий блок. Загальна кількість блоків, необхідних для проведення таблиці, є N = (r/bfr) = 5000000/5 = 1,000,000 блоки

Лінійний пошук в полі ідентифікатора вимагає середнього значення N/2 = 500,000 блокувати доступ, щоб знайти значення, враховуючи, що поле id є ключовим полем. Але оскільки поле ідентифікується також, можна провести бінарний пошук, який потребує середнього значення log2 1000000 = 19.93 = 20 блокування доступу. Миттєво ми бачимо, що це різке поліпшення.

Зараз ім'я поле не відсортовано, ані ключове поле, тому неможливий бінарний пошук, а також значення не є унікальними, і, таким чином, таблиця буде вимагати пошуку до кінця для точного N = 1,000,000 блокування доступу. Саме така ситуація полягає в тому, що індексація має на меті виправлення.

Враховуючи те, що індексний запис містить лише індексоване поле та покажчик на оригінальну запис, вважається, що він буде меншим, ніж багатополезна запис, до якої він вказує. Отже, сам індекс вимагає менше дискових блоків, ніж оригінальна таблиця, і, отже, вимагає меншої кількості блочних доступів для ітерації. Схема для індексу на ім'я поле викладено нижче;

Ім'я поля Тип даних Розмір на диску
firstName Char (50) 50 байт
(рекордний покажчик) Спеціальний 4 байти

Примітка: Покажчики в MySQL мають довжину 2, 3, 4 або 5 байтів у залежності від розміру таблиці.

Приклад 2  - індексування

З огляду на нашу зразкову базу даних r = 5,000,000 записи з довжиною індексу запису в R = 54 байтів і використовуючи розмір блоку за замовчуванням B = 1,024 байтів Коефіцієнт блокування індексу буде bfr = (B/R) = 1024/54 = 18 записи на дисковий блок. Загальна кількість блоків, необхідних для утримання індексу, є N = (r/bfr) = 5000000/18 = 277,778 блоки

Тепер пошук за допомогою ім'я Поле може використовувати індекс для підвищення продуктивності. Це дозволяє для бінарного пошуку індексу з середнім значенням log2 277778 = 18.08 = 19 блокування доступу. Знайти адресу фактичного запису, для чого потрібен подальший доступ до блоку для читання, приведення загальної кількості до 19 + 1 = 20 блокування доступу, далеко від 1000000 блоків доступу, необхідних для пошуку ім'я матч у неіндексованому таблиці.

Коли його слід використовувати?

Враховуючи, що створення індексу вимагає додаткового місця на диску (додатково 277778 блоків з наведеного вище прикладу, збільшення на 28%), і що занадто багато індексів може спричинити проблеми, що випливають із обмежень на розмір файлових систем, слід обережно враховувати правильний вибір поля для індексування.

Оскільки індекси використовуються лише для прискорення пошуку відповідного поля в межах записів, видається підставою для того, що поля для індексування, що використовуються лише для виводу, будуть просто втратою місця на диску та часу обробки при виконанні операції вставки або видалення, а отже слід уникати. Також, враховуючи характер бінарного пошуку, важливою є потужність або унікальність даних. Індексація на полі з потужністю 2 розбиває дані наполовину, тоді як потужність 1000 поверне близько 1000 записів. З такою низькою потужністю ефективність знижується до лінійного сорту, а оптимізатор запитів уникає використання індексу, якщо потужність менше 30% від кількості записів, що фактично робить індекс марною тратою.


2852
2017-08-04 10:41



Бінарний пошук можна зробити, коли дані унікальні, чи правильно я? хоча ви згадали про те, що найменша потужність важлива, алгоритм не був б просто пошуком, як би це наближення (~ log2 n) вплинуло на час процесу? - shampoo
@AbhishekShivkumar: Велике питання! Я думаю, що таблиця індексу буде мати стільки рядків, скільки є в таблиці даних. І оскільки це поле буде мати лише 2 значення (булеві з true / false) і сказати, що ви хочете запис із значенням true, то ви можете лише вдвічі вивести результат, встановлений у першому проході, у другому проході всі ваші записи мають значення true, тому існує немає підстав для диференціації, тепер вам доведеться шукати в таблиці даних в лінійній формі, отже, він сказав, що при виборі індексованого стовпця слід враховувати потужність. У такому випадку не варто вказувати індекс на такий стовпець. Сподіваюся, що я правий :) - Saurabh Patil
Не повинно бути числа блочних звернень у середньому випадку (N+1)/2. Якщо ми підсумовуємо кількість блочних звернень у всіх можливих випадках і поділяємо їх на кількість випадків, то ми маємо N*(N+1)/(2*n) що виходить (N+1)/2. - ajay
Я думаю, що в цій відповіді є декілька помилок, наприклад, у реченні: "далеко від 277 778 блоків доступу, необхідних неіндексованому столу". автор не має на увазі 1000000 блоків доступу? 277 778 - це кількість блоків, необхідних самим індексом. Здається, існує ще пара неточностей :( - jcm
@jcm Він пояснив це в розділі "Що таке секція індексування" - "Індексування - це спосіб сортування ряду записів у декількох полях. Створення індексу на полі в таблиці створює іншу структуру даних, яка містить значення поля, а покажчик до запису, до якої він відноситься. Така структура індексу потім сортується, що дозволяє виконувати двійкові пошуки ". - grinch


Перший раз, коли я прочитав це, це було дуже корисно для мене. Дякую.

З тих пір я отримав певну інформацію про недоліки створення індексів: якщо ви пишете в таблицю (UPDATE або INSERT) з одним індексом, у вас фактично є дві операції запису в файловій системі. Один для даних таблиці та інший для даних індексу (і його вживання (і, якщо кластеризовано, використання даних таблиці). Якщо таблиця та індекс розташовані на тому ж жорсткому диску, це коштує більше часу. Таким чином, таблиця без індексу (куча), дозволить швидше писати операції. (якщо у вас було два індекси, ви могли б мати три операції запису, і так далі)

Однак визначення двох різних місць на двох різних жорстких дисках для даних індексу та табличних даних може зменшити / усунути проблему збільшення витрат часу. Для цього потрібні визначення додаткових груп файлів з відповідними файлами на бажаних жорстких дисках та визначенням розташування таблиці / індексу за бажанням.

Інша проблема з показниками - це їх фрагментація з часом, коли дані вставляються. REORGANIZE допомагає, ви повинні написати процедури, щоб зробити це.

У певних сценаріях купа корисніше, ніж таблиця з індексами,

наприклад: - Якщо у вас багато письмових конкурентів, але лише за один вечір читайте за межами робочого часу для звітування.

Також досить важливою є диференціація кластеризованих та некластованих показників.

Допомагав мені: - Що означають кластеризовані та некластеризовані індекси?


176
2018-04-30 14:31



Я думаю, ці проблеми індексації можуть бути вирішені шляхом підтримки двох різних баз даних, як Майстер і Slave. Де Майстер може бути використаний для вставки або оновлення записів. Без індексації. І раб може бути використаний для читання з належним індексом правильно ??? - bharatesh
ні, неправильно, вибачте. Необхідно оновлювати не тільки зміст таблиць, але також структуру та зміст індексу (b-дерево, вузли). Ваша концепція майстра і рабів тут не має сенсу. що може бути здійснено, хоча це реплікація або віддзеркалення другої бази даних, на якій відбувається аналітика, щоб відібрати цю навантаження далеко від першої бази даних. ця друга база даних буде зберігати копії даних і індекси на ці дані. - Der U
Я ...! Спробуйте прочитати мій коментар і зрозуміти це належним чином. Я також говорив про те ж саме, я мав на увазі майстра та ведомого (що завгодно), як "виявлення або віддзеркалення другої бази даних, на якій відбувається аналітика, щоб відібрати цей робочий навантаження від першої бази даних. Ця друга база даних буде зберігати копії даних та індексів на що дані " - bharatesh
друга база даних, до якої здійснюється дзеркальне відтворення або реплікація, підлеглий - буде відчувати всю маніпуляцію даними, як це робить перша. з кожною операцією DML індекси на цю другу базу даних будуть відчувати "ці проблеми індексування". я не бачу коефіцієнта корисної дії, де де-небудь необхідні індекси та побудовані для швидкого аналізу, вони повинні бути актуальними. - Der U


Індекс - це просто структура даних, яка робить пошук швидше для певного стовпця в базі даних. Ця структура, як правило, є b-деревом або хеш-таблицею, але це може бути будь-яка інша логічна структура.

Для отримання додаткової інформації рекомендую: Як працюють індекси бази даних? І, як допомагають індекси?


131
2018-02-20 14:40



+1 раз на мільйон за цю відповідь, тому що я знайшов цей список, намагаючись знайти просте пояснення того, що таке індексація. - Josh Burson


Тепер, скажімо, ми хочемо запустити запит, щоб знайти всі подробиці всіх працівників, які називаються "Abc"?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Що буде без індексу?

Програмне забезпечення баз даних повинно було буквально переглянути кожен рядок у таблиці працівників, щоб побачити, чи ім'я роботодавця для цього рядка є «Abc». І тому, що ми хочемо, щоб у кожному рядку з назвою "Abc" в ній, ми не можемо просто зупинитися, коли ми знайдемо лише один рядок з назвою "Abc", оскільки можуть бути інші рядки з назвою Абс. Тому треба шукати кожен рядок до останнього рядка - це означає, що тисячі рядків у цьому сценарії повинні бути перевірені базою даних, щоб знайти рядки з назвою "Abc". Це те, що називається а сканування повного столу

Як індекс бази даних може допомогти продуктивності

Вся справа в індексі полягає в тому, щоб прискорити пошукові запити, суттєво скоротивши кількість записів / рядків у таблиці, які необхідно розглянути. Індекс - це структура даних (найчастіше дерево B), яка зберігає значення для певного стовпця в таблиці.

Як працює індекс B-trees?

Причина B-дерева є найпопулярнішою структурою даних для індексів, пов'язана з тим, що вони є ефективними в часі, оскільки пошук, видалення та вставки можуть бути виконані в логарифмічний час. І ще одна з найважливіших причин B-дерев, що частіше використовуються, полягає в тому, що дані, що зберігаються в дереві B, можуть бути відсортовані. СУБД, як правило, визначає, яка структура даних насправді використовується для індексу. Але в деяких сценаріях з деякими RDBMS ви можете вказати, яку структуру даних ви хочете використовувати вашу базу даних при створенні самого покажчика.

Як працює індекс таблиці хеш?

Причиною хеш-індексів є те, що таблиці хешів є надзвичайно ефективними, коли мова йде лише про підвищення цінностей. Отже, запити, які порівнюють за рівністю до рядка, можуть дуже швидко отримувати значення, якщо вони використовують хеш-індекс.

Наприклад, запит, який ми обговорювали раніше, може скористатися хеш-індексом, створеним у стовпці Employee_Name. Те, як буде працювати індекс хешу, полягає в тому, що значення стовпця буде ключовим у таблиці хешу, а фактичне значення, накладене на цей ключ, буде просто покажчиком на дані рядка в таблиці. Оскільки хеш-таблиця в основному являє собою асоціативний масив, типовий запис буде виглядати приблизно так: "Abc => 0x28939", де 0x28939 є посиланням на рядок таблиці, де Abc зберігається в пам'яті. Отримання такого значення, як "Abc" в індексі хеш-таблиці, і повернення посилання на рядок у пам'яті, очевидно, набагато швидше, ніж сканування таблиці, щоб знайти всі рядки з значенням "Abc" у стовпці Ім'я роботодавця.

Недоліки хеш-індексу

Хеш-таблиці не відсортовані структури даних, і існує безліч типів запитів, які навіть не можуть допомогти в хеш-індексах. Наприклад, припустімо, ви хочете дізнатись про всіх працівників, яким виповнилося менше 40 років. Як ви могли це зробити за індексом хеш-таблиці? Ну, це не можливо, тому що хеш-таблиця добре підходить для пошуку ключових пар значень - це означає запити, які перевіряють рівність

Що саме знаходиться в індексі бази даних? Отже, тепер ви знаєте, що індекс бази даних створено в стовпці таблиці, а індекс зберігає значення в цьому конкретному стовпці. Але важливо зрозуміти, що індекс бази даних не зберігає значення в інших стовпцях тієї ж таблиці. Наприклад, якщо ми створимо індекс у стовпці Employee_Name, це означає, що значення в стовпці Employee_Age та Employee_Address також не зберігаються в індексі. Якщо б ми просто зберігали всі інші стовпці в індексі, то це було б просто як створення ще однієї копії всієї таблиці - це займе надто багато місця і буде дуже неефективним.

Як база даних знає, коли використовувати індекс? Коли запускається запит типу "SELECT * FROM Employee WHERE Employee_Name = 'Abc'", база даних буде перевіряти наявність індексу у стовпцях, що запитуються. Припускаючи, що стовпець Employee_Name має індекс, створений на ньому, базі даних доведеться вирішувати, чи дійсно є сенс використовувати індекс для пошуку шуканих значень - оскільки є кілька сценаріїв, де насправді менш ефективно використовувати індекс бази даних , і більш ефективно просто сканувати всю таблицю.

Скільки коштує індекс бази даних?

Це займає місце - і чим більше ваш стіл, тим більше ваш індекс. Ще одним показом, який потрапляє в індекси, є той факт, що кожного разу, коли ви додасте, видаляєте або оновлюєте рядки у відповідній таблиці, вам доведеться виконувати ті самі операції, що й до вашого індексу. Пам'ятайте, що індекс повинен містити однакові дані за хвилину, як у стовпцях таблиці, які охоплює індекс.

Як правило, індекс повинен бути створений лише на стіл, якщо дані в індексованому стовпчику будуть часто запитуватися.

Дивись також

  1. Які стовпці зазвичай роблять хороші показники?
  2. Як працюють індекси бази даних

94
2017-08-13 18:36



"індекс бази даних не зберігає значення в інших стовпчиках" - невірно. - mustaccio
@mustaccio: Індекс зберігає довідник рядка лише з індексованими стовпцями (наскільки я знаю). Я можу помилятися Чи є у вас посилання, яке говорить, що індекс зберігає інші значення стовпців? - Somnath Muluk
@ Для людей з обмеженими можливостями: Чи можете ви просто пояснити, що не так, щоб я міг поліпшити? - Somnath Muluk
Перевірте, наприклад, класифіковані індекси SQL Server або DB2 CREATE INDEX ... INCLUDE пост. На мою думку, ви маєте надто багато узагальнень у вашій відповіді. - mustaccio
@mustaccio: Так за замовчуванням create index не включає інші стовпці і чому це слід. If we did just store all the other columns in the index, then it would be just like creating another copy of the entire table, which would take up way too much space and would be very inefficient.. Це більш узагальнена версія індексів. CREATE INDEX ... INCLUDE це нова версія, розглядаючи інші стовпці. Пост, який я пояснив, розглядає більш загальну версію. Як індекси працюватимуть однією книгою, якщо ми розглянемо всі бази даних? Чи не так? Ви думаєте, що відповідь заслуговує на зниження? - Somnath Muluk


Класичний приклад "Індекс у книгах"

Розглянемо "Книгу" з 1000 сторінок, поділена на 100 розділів, кожний розділ з X сторінками.

Просто, а?

Тепер, якщо немає індексної сторінки, для пошуку певного розділу, який починається з букви "S", у вас немає іншого вибору, окрім сканування через всю книгу. тобто 1000 сторінок

Але з початковою сторінкою ви знаходитесь там. І ще, щоб прочитати будь-який конкретний розділ, який важливо, вам просто потрібно переглядати сторінку індексу, знову і знову, кожного разу. Після пошуку відповідного індексу ви можете ефективно перейти до розділу, пропустивши інші розділи.

Але тоді, крім 1000 сторінок, для відображення індексної сторінки вам знадобиться ще ~ 10 сторінок, тобто всього 1010 сторінок.

Таким чином, індекс є окремим розділом, який зберігає значення індексованого стовпця + покажчик на індексований рядок у відсортованому порядку для ефективних пошуків.

У школах все просто, чи не так? : П.


86
2018-04-23 14:43



дуже гарна аналогія! весело, я не зробив зв'язку між індексом книги та індексом db - Yolo Voe
Красиве пояснення для швидкого розуміння: D - ndh103


Простий опис !!!!!!!!!!

Індекс - це не що інше, як структура даних, яка зберігає значення для певного стовпця в таблиці. Індекс створюється в стовпці таблиці.

Наприклад, у нас є таблиця бази даних, яку називають користувачем, з трьома стовпцями - ім'я, вік, і адреса. Припустимо, що таблиця User має тисячі рядків.

Тепер, скажімо, ми хочемо запустити запит, щоб знайти всі подробиці всіх користувачів, які називаються "Джон". Якщо ми виконаємо наступний запит.

SELECT * FROM User 
WHERE Name = 'John'

Програмне забезпечення бази даних повинно буквально переглядати кожен рядок у таблиці «Користувач», щоб побачити, чи ім'я для цього рядка є «Джон». Це займе багато часу.
Саме там, де індекс допомагає нам, "індекс використовується для прискорення пошукових запитів шляхом суттєвого скорочення кількості записів / рядків у таблиці, яка потребує перевірки".
Як створити індекс

CREATE INDEX name_index
ON User (Name)

Індекс складається з значень стовпчиків (наприклад, Джон) з однієї таблиці, і ці значення зберігаються в структурі даних.
Отже, тепер база даних використовуватиме індекс для пошуку співробітників під назвою Джон, оскільки індекс, імовірно, буде відсортовано в алфавітному порядку за ім'ям користувача. І тому, що він сортується, це означає, що пошук назви набагато швидше, оскільки всі імена, починаючи з "J", будуть прямо поруч один з одним в індексі!


47
2017-08-02 01:30





Просто швидка пропозиція. Оскільки витрати на індексування додатково записуються та зберігаються, то якщо ваша програма потребує більше операцій вставки / оновлення, можливо, вам знадобиться використовувати таблиці без індексів, але якщо для цього потрібні додаткові операції з пошуку даних, вам слід перейти на індексування стіл


21
2018-01-14 06:44



Це коментар, а не відповідь. - RonJohn


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

Коротше кажучи, індекс - це структура даних, яка зберігає значення для певного стовпця в таблиці, щоб пришвидшити пошук запитів.


16
2017-12-21 17:16





Індекс SQL - це щось, пов'язане з прискоренням пошуку в базі даних SQL. Індекс дозволяє програмісту швидко завантажувати дані з бази даних. Припустимо, ви студент чи читач книг. Ваша книга містить 50 000 сторінок. Перший день, коли ви читаєте тему "ABC", наступного дня ви хочете прочитати іншу тему "xyz". ви ніколи не будете вручну проходити сторінку по сторінці. Що ви будете робити в цій ситуації, це використовувати індекс книги, щоб переглянути певну тему, а потім перейти безпосередньо до вашої теми. Індекс створив багато часу для пошуку теми. Те ж саме в індексі SQL, Index дозволяє швидко шукати мільйони записів з бази даних.


10
2018-02-15 10:17





Індекс бази даних - це структура даних, яка покращує швидкість операцій з пошуку даних у таблиці бази даних за рахунок додаткових записів та місця для зберігання даних для збереження структури даних індексу. Індекси використовуються для швидкого пошуку даних без необхідності пошуку кожного рядка в таблиці бази даних при кожному зверненні до таблиці бази даних. Індекси можуть бути створені за допомогою одного або декількох стовпчиків таблиці бази даних, що є основою для швидких випадкових пошуків та ефективного доступу до замовлених записів.


1
2017-07-09 05:33