Обычно это B-дерево или его варианты, в основном потому, что оно упаковывает узлы в блоки, в отличие от двоичных деревьев, таких как AVL.
Узел B-дерева имеет фиксированный максимальный размер и содержит несколько ключей и несколько указателей на дочерние узлы, что означает, что для поиска значения необходимо извлечь меньше дисков с диска (по сравнению с двоичным деревом).
Статья в Википедии о B + деревьях имеет хорошее введение с точки зрения ее применения к базам данных.