B+ деревья

Вариант B-дерева: только листья хранят данные (или указатели на записи), внутренние узлы — только ключи для навигации. Листья связаны в linked list (быстрый range scan). Преимущества: больше ключей во внутренних узлах (меньше высота), эффективные range queries (сканируем листья последовательно без возврата к корню). Используется InnoDB (MySQL), PostgreSQL (по умолчанию), SQLite. Вставка/удаление: split (узел переполнен — делим пополам, median key поднимаем), merge (узел underflow — сливаем с соседом)