Indexování databáze v kostce s porovnáním B+strom a hash

Lidé se často říkají, že indexování je běžná technika pro efektivní zpracování dotazů v případě, že je vaše databáze dostatečně velká. Tento příspěvek je pro shrnutí toho, co je index databáze, a pro přehodnocení hash a B+stromu.

Index je datová struktura, která organizuje záznamy za účelem optimalizace určitých druhů operací vyhledávání. Můžeme vytvořit index na poli tabulky a poté načíst všechny záznamy, které splňují podmínky vyhledávání na search-key pole. Bez indexu by náš dotaz skončil lineárním skenováním celého obsahu tabulky, abychom získali pouze jeden nebo několik záznamů.

V tomto příspěvku bych rád shrnul výkon a případy použití dvou běžných technik indexování:Hash index a B+strom

Index hash

Tato technika je široce používána pro vytváření indexů v hlavní paměti protože jeho rychlé získávání od přírody. Má průměrnou složitost operace O(1) a složitost úložiště O(n).
V mnoha knihách lidé používají termín bucket k označení jednotky úložiště, která uchovává jeden nebo více záznamů
Pokud jde o hašování, je třeba diskutovat o dvou věcech:

• Hashovací funkce:mapuje vyhledávací klíče (jako svůj vstup) na celé číslo představující daný klíč v segmentu.
• Schéma hašování:jak se vypořádat s kolizí klíčů po hašování.

Někteří lidé se ptají:proč kolize? Existuje někdy dokonalá hašovací funkce? Ve skutečnosti, řekněme, že vaše klíče jsou nekonečnou množinou, je nemožné je namapovat na množinu 32bitových celých čísel, aniž by nedošlo ke kolizi. Mezi výpočtem a četností kolizí by měl existovat kompromis.

Za zmínku stojí několik hašovacích schémat:lineární sondování, řetězené hašování a rozšiřitelné hašování. Algoritmy vyhledávání/vkládání/mazání se liší podle schématu hašování, například zřetězené hašování řeší kolize klíčů umístěním prvků se stejnou hašovací hodnotou do stejného segmentu.

Klady

• Hash index je vhodný pro vyhledávání rovnosti nebo primárního klíče. Dotazy mohou těžit z hash indexu k získání amortizovaných O(1) nákladů na vyhledávání. Například:SELECT name, id FROM student WHERE id = '1315';

Nevýhody

Tabulka hash má určitá omezení:

• Dotazy na rozsah nejsou efektivní. Hash tabulka je založena na rovnoměrném rozdělení. Jinými slovy, nemáte žádnou kontrolu nad tím, kam bude položka rejstříku umístěna.
• Nízká škálovatelnost:výkon vyhledávací operace se může snížit, pokud dojde k velkému množství kolizí, a to vyžaduje změnu velikosti hashovací tabulky a přepracování existujících položek indexu.

B+strom

Jedná se o samovyvažující stromovou datovou strukturu, která udržuje data v seřazeném pořadí a umožňuje rychlé vyhledávání v rámci každého uzlu, obvykle pomocí binárního vyhledávání.
B+Tree je standardní implementace indexu v téměř všech relačních databázových systémech.

B+Tree je v podstatě M-way vyhledávací strom, který má následující strukturu:

• dokonale vyvážené:listové uzly mají vždy stejnou výšku.
• každý vnitřní uzel kromě kořene je alespoň z poloviny plný (M/2 − 1 <=počet klíčů <=M − 1).
• každý vnitřní uzel s k klíči má k+1 nenulových potomků.

Každý uzel stromu má pole seřazených párů klíč–hodnota. Pár klíč-hodnota je vytvořen z (hledaná hodnota klíče, ukazatel) pro kořenové a vnitřní uzly. Hodnoty listového uzlu mohou být 2 možnosti:

• skutečný záznam
• ukazatel na skutečný záznam

Vyhledejte hodnotu v

• Začněte s kořenovým uzlem
• I když uzel není listový uzel, děláme:
  • Najděte nejmenší Ki, kde Ki>=v
  • Pokud Ki ==v:nastavte aktuální uzel na uzel označený Pi+1
  • V opačném případě nastavte aktuální uzel na uzel označený pí

Duplicitní klíče

Obecně platí, že vyhledávací klíč může být duplicitní, aby se to vyřešilo, většina databázových implementací přichází se složeným vyhledávacím klíčem. Například chceme vytvořit index na student_name pak by náš složený klíč vyhledávání měl být (jméno_studenta, Ap), kde Ap je primární klíč tabulky.

Klady

B+tree nabízí dvě hlavní funkce:

• Minimalizace I/O operací
  • Snížená výška:B+Tree má poměrně velký faktor větvení (často používaná hodnota mezi 50 a 2000), díky čemuž je strom tlustý a krátký. Obrázek níže ilustruje B+Strom s výškou 2. Jak vidíme, uzly jsou rozprostřeny, k přechodu dolů k listu je zapotřebí méně uzlů. Cena za vyhledání jedné hodnoty je výška stromu + 1 pro náhodný přístup k tabulce.
• Škálovatelnost:
  • Máte předvídatelný výkon pro všechny případy, zejména O(log(n)). U databází je to obvykle důležitější než lepší nejlepší nebo průměrný výkon případu.
  • Strom vždy zůstává vyvážený svou implementací. B+Strom s n klíči má vždy hloubku O(log(n)). Výkon se tedy nesníží, pokud se databáze zvětší. Čtyřúrovňový strom s faktorem větvení 500 může uložit až 256 TB za předpokladu, že stránka má velikost 4 kB.

• B+Tree je nejvhodnější pro dotazy na rozsah, například "SELECT * FROM student WHERE age > 20 AND age < 22"

Závěr

Ačkoli hash index funguje lépe, pokud jde o dotazy na přesnou shodu, B+Tree je pravděpodobně nejpoužívanější indexovou strukturou v RDBMS díky svému konzistentnímu celkovému výkonu a vysoké škálovatelnosti.

V poslední době přitahuje značný zájem log-strukturovaný slučovací strom (LSM-tree) jako uchazeč o B+-strom, protože jeho datová struktura by mohla umožnit lepší efektivitu využití úložného prostoru. Budu to dále zkoumat a v blízké budoucnosti o tom uveřejním příspěvek.