B-дерево и B+-дерево

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

Подробнее: Каждый узел соответствует странице хранилища (например, 8 КБ) и содержит сотни ключей. Поэтому дерево очень плоское: за 3–4 уровня находят один элемент среди миллионов. В B+-дереве все данные лежат в листьях, связанных друг с другом, что ускоряет запросы по диапазону.