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