Индексиране на база данни накратко с B+tree и Hash в сравнение

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

Индексът е структура от данни, която организира записи за оптимизиране на определени видове операции за извличане. Можем да създадем индекс в поле на таблицата, след което да извлечем всички записи, които отговарят на условията за търсене на search-key поле. Без индекс нашата заявка ще сканира линейно цялото съдържание на таблицата, за да извлече само един или няколко записа.

В тази публикация бих искал да обобщя ефективността и случаите на използване на две често срещани техники за индексиране:Хеш индекс и В+дърво

Хеш индекс

Тази техника се използва широко за създаване на индекси в главната памет тъй като бързото му извличане по природа. Той има средна O(1) операционна сложност и O(n) сложност на съхранение.
В много книги хората използват термина bucket за да се обозначи единица за съхранение, която съхранява един или повече записи
Има две неща за обсъждане, когато става въпрос за хеширане:

• Хеш функция:съпоставя ключовете за търсене (като своя вход) в цяло число, представляващо този ключ в кофата.
• Схема за хеширане:как да се справим с сблъсък на ключове след хеширане.

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

Има няколко схеми за хеширане, които си струва да се спомене:линейно сондиране, верижно хеширане и разширяемо хеширане. Алгоритмите за търсене/вмъкване/изтриване варират според схемата на хеширане, например, верижно хеширане се справя с ключови колизии чрез поставяне на елементите имат една и съща хеш стойност в една и съща кофа.

Плюсове

• Хеш индексът е подходящ за търсене на равенство или първичен ключ. Заявките могат да се възползват от хеш индекса, за да получат амортизирани разходи за търсене O(1). Например:SELECT name, id FROM student WHERE id = '1315';

Против

Хеш таблицата има някои ограничения:

• Заявките за диапазон не са ефективни. Хеш таблицата се основава на равномерно разпределение. С други думи, нямате контрол върху това къде ще бъде поставен индекс.
• Ниска мащабируемост:производителността на операцията за търсене може да се влоши, когато има много сблъсъци и изисква преоразмеряване на хеш таблицата, след което повторно хеширане на съществуващите записи в индекса.

B+Дърво

Това е самобалансираща се структура от данни в дърво, която поддържа данните в сортиран ред и позволява бързо търсене във всеки възел, обикновено използвайки двоично търсене.
B+Tree е стандартна реализация на индекси в почти всички системи за релационни бази данни.

B+Tree е основно M-посочено дърво за търсене, което има следната структура:

• перфектен баланс:листните възли винаги имат една и съща височина.
• всеки вътрешен възел, различен от корена, е пълен поне наполовина (M/2 − 1 <=брой ключове <=M − 1).
• всеки вътрешен възел с k ключове има k+1 ненулеви деца.

Всеки възел на дървото има масив от сортирани двойки ключ-стойност. Двойката ключ-стойност е конструирана от (стойност на ключ за търсене, указател) за основни и вътрешни възли. Стойностите на листовия възел могат да бъдат 2 възможности:

• действителния запис
• указателят към действителния запис

Потърсете стойност v

• Започнете с главен възел
• Докато възелът не е листен възел, ние правим:
  • Намерете най-малкото Ki, където Ki>=v
  • Ако Ki ==v:задайте текущия възел на възела, посочен от Pi+1
  • В противен случай задайте текущия възел на възел, посочен от Pi

Дублиращи се ключове

Като цяло, ключът за търсене може да бъде дублиран, за да се реши това, повечето реализации на база данни предлагат съставен ключ за търсене. Например, ние искаме да създадем индекс на student_name тогава нашият съставен ключ за търсене трябва да бъде (име_ученик, Ap), където Ap е първичният ключ на таблицата.

Плюсове

Има две основни функции, които B+tree предлага:

• Минимизиране на I/O операции
  • Намалена височина:B+Tree има доста голям коефициент на разклоняване (често използвана стойност между 50 и 2000), което прави дървото дебело и ниско. Фигурата по-долу илюстрира B+Tree с височина 2. Както виждаме, че възлите са разпръснати, са необходими по-малко възли за преминаване надолу до лист. Цената за търсене на една стойност е височината на дървото + 1 за произволния достъп до таблицата.
• Мащабируемост:
  • Имате предвидима производителност за всички случаи, в частност O(log(n)). За базите данни обикновено е по-важно от това да имат по-добра най-добра или средна производителност на случаите.
  • Дървото винаги остава балансирано от изпълнението си. B+Tree с n ключа винаги има дълбочина O(log(n)). По този начин производителността няма да се влоши, ако базата данни нарасне. Дърво на четири нива с коефициент на разклоняване 500 може да съхранява до 256 TB, при условие че размерът на страницата е 4KB.

• B+Tree е най-подходящ за заявки за диапазон, например "SELECT * FROM student WHERE age > 20 AND age < 22"

Заключение

Въпреки че хеш индексът се представя по-добре по отношение на заявките за точно съвпадение, B+Tree е може би най-широко използваната структура на индекса в RDBMS благодарение на постоянната си производителност в цялостната и висока мащабируемост.

Напоследък дървото за сливане с логаритмична структура (LSM-дърво) привлече значителен интерес като претендент за B+-дървото, тъй като неговата структура от данни може да позволи по-добра ефективност при използване на пространството за съхранение. Ще го проуча допълнително и ще направя публикация за него в близко бъдеще.