[ 用户 chunhui 在转载时对文章内容进行了编辑 ]

发信人: chunhui (北瓜), 信区: Programming
标  题: 请问一个数据库索引的问题
发信站: 水木社区 (Thu May 30 17:24:43 2024), 站内

比如这种情况：
记录写入了一个文件。索引写入另一个文件。记录的key唯一。这时候，索引可以是一个树，查询到的结果对应一个唯一的key（和记录的位置）。

但是有这种情况：
记录有多个。key有一个。安装上面的思路，那索引树的结果就需要指向多个记录的位置。

这种情况如果在内存里还好处理。多个位置也就是一个动态数组或者链表。来新的就申请空间即可。但是索引是存在文件中的话，就非常难办。

想问一下，这种情况在数据库里应该是一个常见的模式，有什么标准常规的办法来处理这种情况呢？

b+树我看书上也没有提到重复键值的问题。即便可以插入重复键值，但是查找的时候还有一个要求，就是要定位到第一个值，然后遍历得到所有的值。

当然，我不一定非要用b+树解决重复键值的问题。其他办法也可以。也可以b+树定位到值表，这个值表保持多个键值。但是这个保存多个值的表也会面临在一纬的文件空间上如何动态增长多个键值的问题。而且我想在写入的时候不用读写磁盘。写完之后批量一次写入磁盘。如果允许在写入的时候读写磁盘，就没这么麻烦了。

感觉这应该是数据库中很常见的问题，请问有没有相关的资料推荐？多谢。
--
修改:chunhui FROM 125.33.237.*
FROM 103.90.179.*

多谢。我现在基本上已经有办法了。再琢磨一下哪个更简单一些。
基本思路就是：让一个val上可以挂多个重复值，或者key上加其他标号,使其唯一。
【 在 jimmycmh 的大作中提到: 】
: 二级索引。一级索引里记录二级索引的位置，二级索引里记记录的位置
: 添加记录的时候，新建一个二级索引item，然后更新一级索引
: 时间久了，二级索引里会有很多死记录，定期再重建。
: ...................
--
修改:chunhui FROM 117.133.52.*
FROM 117.133.52.*

这样不行，数据量太大，无法放到内存里。我这个现在的索引都是打算先部分在内存，然后刷新到磁盘。

直接用rocksdb这样的数据库来存索引也是可以的。但这里有太多我不需要的东西。
【 在 mango7788 的大作中提到: 】
: 搞个内存里的数据库呗。
: 搞集成会花些时间，但可能会省去开发算法所花的时间。
--
FROM 117.133.52.*

多谢。我去找找看。我目前想用跳表来实现。跳表支持重复键值比较好处理。

跳表读不如b+树。但是b+树再写入的时候不如跳表快，而且支持重复键值比较麻烦也浪费空间。
【 在 ylh0315 的大作中提到: 】
: 以前有一个ISAM（Index Sequence Access Method)，能完成你这个工作，我用过。
: 多用户并发，完全的B+树索引。
: 支持多个索引，每个索引可以多个部分组成，每个部分可以分别按增序或降序排序。每个索引都可以是唯一或不唯一。
: ...................
--
FROM 117.133.52.*

我不是找这样的数据库，我是想知道他们的实现方式。否则可以直接用rocksdb。
目前基本确定用跳表。跳表挂上重复的键值相对简单一点。b+树如何支持重复键值，搜的资料都一笔带过。说是用overflow page。而且这个办法浪费空间。。。。
【 在 Madlee 的大作中提到: 】
: berkelydb  gnudb ....
: 有很多这样简单的key-value数据库
--
修改:chunhui FROM 111.196.134.*
FROM 111.196.134.*