Простой вопрос: почему таблица базы данных не реализована с использованием массива или динамического массива (например, вектора в c ++), а, например, с помощью дерева сплайнов (или B-дерева в этом отношении)?
Мои рассуждения:
Данные кластерных деревьев Splay используются последними и часто верхними, что хорошо, но это свойство может создавать O (n) ситуаций, поэтому его необходимо время от времени перебалансировать (скажем, при операции поиска). Перебалансировка частично разрушает указанное выше свойство, и при перебалансировке оно может вызвать провал в ответ. B-дерево, вероятно, чаще всего является базовым представлением, но все еще демонстрирует log (n) и отклик в определенных ситуациях, не предлагая кластеризацию данных.
Если бы вместо этого использовался динамический массив, все значения CRU в данных были бы равны O (1), за исключением изменения размера памяти время от времени (что при некотором интеллектуальном предварительном распределении, возможно, может происходить перемещение, когда нет вычислений и т. Д., Я думаю оказал нулевое воздействие). Единственной проблемой было бы удаление, но, по моему опыту, большинство данных (если таблица не является таблицей отношений или временными данными ...) даже не удаляются, а просто становятся недействительными, поскольку их можно повторно использовать для анализа. При представлении в виде дерева и т. Д. Вы вынуждены разбивать недействительные данные на отдельные таблицы, чтобы сохранить скорость и т. Д., В случае с массивом, который даже не имеет значения, поскольку эксплуатационные расходы не изменятся с расширением базы данных. Только если будет создано много временных данных, проблема будет заключаться в недействительности вместо удаления.
Так что, возможно, было бы разумно иметь возможность выбрать то, что я хочу, в качестве базовой структуры моей таблицы базы данных (возможно ли это на самом деле)? Когда мы говорим о миллиардах записей и учитываем скорость дисков и переходов, log (n) против O (1) - это большая разница.
В чем подвох?