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