我正在寻找大量记录（超过 40 万条记录）的软件表示
每条记录有两个键。一个用于下限，一个用于上限。这些数字代表一个范围。此外，每条记录都有一些信息，我们称之为 I 。换句话说，每条记录都聚合了共同的项目索引，并有一些关于它们的共同描述。
我的软件有一个项目编号，我必须检索有关它的信息。
我想到了 AVL、B-Tress 或 fibonaci。但我敢肯定，对于这么多的记录来说，哪一个是最好的。对于小型数据库，我肯定会选择 AVL / 平衡 AVL。
问问题
342 次
2 回答
1
任何数据库都会做你想做的事。
如果您在索引上搜索，从 2 条记录到 4 条记录时查找速度的提高与从 200 万条记录到 400 万条记录相同……再上一层……这是指数关系.
于 2011-11-19T13:33:01.883 回答
1
从数据结构的角度来看，您搜索的是区间树。
维基百科的文章非常好。你可以做的是增加一个（平衡的）二叉搜索树，比如 AVL 或 Red-Black-Trees 之类的。基于二叉搜索树的区间树在Cormen 等人的经典 DS 书中有自己的部分。.
一个好的数据结构可以很好地扩展到大量数据。主要目录操作的复杂度为 O(k + log n)，其中 n 是树中间隔的数量，k 是范围内重叠间隔的数量。这通常很好。它随着区间项目的数量而缓慢增长，除了很多或大多数区间与所有其他区间重叠的情况。
如果您无法将数据保存在主内存中，那么 B-Tree 将是一个不错的选择。
于 2011-11-19T13:49:06.860 回答