B-дерево та B+-дерево

Коротко: B-дерева — збалансовані дерева пошуку з багатьма ключами у вузлі. Вони лежать в основі більшості індексів баз даних, бо потребують мало звернень до диска.

Докладніше: Кожен вузол відповідає сторінці сховища (наприклад, 8 КБ) і містить сотні ключів. Тому дерево дуже пласке: за 3–4 рівні знаходять один елемент серед мільйонів. У B+-дереві всі дані лежать у листках, пов’язаних між собою, що прискорює запити за діапазоном.