Какую структуру данных я должен использовать для представления большого количества записей, каждый из которых представляет диапазон элементов?

Question

Я ищу программное обеспечение представление для очень большого количества записей (более 400К записей)

Каждая запись имеет два ключа.один для нижней границы и один для верхней границы.Эти числа представляют диапазон.Кроме того, каждая запись имеет некоторую информацию, назовем ее IДругими словами, каждая запись объединяет общие индексы элементов и имеет общее описание о них.

Моему программному обеспечению присвоен номер элемента, и я должен получить эту информацию об этом.

Я думал об AVL, B-Tress или фибоначчи.Но я уверен, что это будет лучшим для такого большого количества записей.Я бы определенно пошел на AVL / сбалансированный AVL для небольшой базы данных.

Answer 1

С точки зрения структуры данных, вы ищете дерево интервалов .

Статья в Википедии довольно хорошая.Что вы можете сделать, это расширить (сбалансированное) дерево бинарного поиска, например, AVL или Red-Black-Trees.Деревья интервалов, основанные на бинарном дереве поиска, имеют собственный раздел в классической книге DS Cormen et al. .

Хорошая структура данных хорошо масштабируется для больших объемов данных.Сложность для основных операций с каталогами: O (k + log n), где n - количество интервалов в дереве, а k - количество перекрывающихся интервалов в диапазоне.Это обычно довольно хорошо.Он медленно растет с количеством элементов интервалов, за исключением случаев, когда множество или большинство интервалов перекрывают все остальные.

Если вы не можете хранить свои данные в основной памяти, B-Tree будет хорошим выбором.

Answer 2

Любая база данных будет делать то, что вы хотите, просто отлично.

Если вы выполняете поиск по индексу, увеличение скорости поиска при переходе от 2 до 4 записей аналогично переходу с 2 млн. До 4 млн. Записей ... еще на один уровень к дереву ... это экспоненциальные отношения.