Prečo sa najčastejšie používa index B-stromu a aká je jeho algoritmická zložitosť?

Index B-stromu sa široko se používa v databázach kvôli svojej vyváženej štruktúre, ktorá zabezpečuje efektívne vyhľadávanie, vkladanie a mazanie dát. Hlavným dôvodom popularity B-stromu je jeho schopnosť udržiavať zoradené dáta a rýchlo vykonávať rozsahové dotazy.

Algoritmická zložitosť hlavných operácií v B-strome:

• Vyhľadávanie: O(log n)
• Vkladanie: O(log n)
• Vymazanie: O(log n)

Kde n je počet prvkov v indexe. Táto logaritmická zložitosť sa dosahuje tým, že strom je vyvážený a výška stromu rastie pomaly s rastom dát.