После некоторых исследований и чтения статей я нашел ответ.
Чтобы справиться с большими объемами данных, такими как миллионы записей, индексы должны быть организованы в кластеры.Кластер - это непрерывная группа секторов на диске, которую можно быстро прочитать в память.Обычно они имеют длину около 4096 байт.
Если мы организуем наш индекс так, чтобы каждый из этих кластеров содержал упорядоченный список индексов, которые указывают на данные на диске (кластер данных), у нас может быть упорядоченный индекс списка.
Итак, если мы ищем конкретную запись, как мы узнаем, в каком кластере она находится?Мы выполняем бинарный поиск, чтобы найти рассматриваемый кластер [O (log n)].
Однако, чтобы выполнить бинарный поиск, нам нужно знать диапазон значений в каждом кластере данных, поэтому нам нужны метаданные, в которых указано минимальное и максимальное значение каждого кластера и где находится этот кластер.Это замечательно.За исключением случаев, когда каждый кластер данных содержит 100 индексов, а наш кластер метаданных также содержит 100 индексов, мы можем получить доступ только к 100 кластерам данных.Что соответствует 10 000 записей (100 X 100).
Ну, этого недостаточно.Давайте добавим еще один кластер метаданных, и теперь мы можем получить доступ к 1 000 000 записей.Итак, как мы узнаем, какой из трех кластеров метаданных нам нужно запросить, чтобы найти целевой кластер данных.Мы могли бы искать их один за другим, но это не масштабируется, и его O (n / 2) в среднем.Поэтому я добавляю еще один кластер мета-метаданных, чтобы указать, какой из трех кластеров метаданных мне нужно запросить, чтобы найти целевой кластер данных.Теперь у меня есть дерево!
Так вот почему базы данных используют деревья.Это не скорость, это размер индексов и необходимость иметь индексы, ссылающиеся на другие индексы.Выше я описал дерево B + - дочерние узлы содержат ссылки на другие дочерние узлы или конечные узлы, а конечные узлы содержат ссылки на данные на диске.
Фу!