背景：我将插入大约十亿个键值对。我需要一个内存索引，我可以使用它同时查找（唯一的，64 位整数）键的（32 位整数）值。没有更新，没有删除，没有遍历。键通常随着时间逐渐增加。
什么索引结构最适合处理这个问题？
我能想到的要求是：
- 由于密钥的增加，它需要进行有效的再平衡
- 它需要有效地使用内存以适应内存，最好 < 28GB
- 它需要有非常有效的查找
问问题
1563 次
1 回答
0
对于这个问题，可能没有比简单的排序向量更有效的数据结构了。（实际上，考虑到对齐问题并根据访问特性，您可能希望将键和值放在单独的向量中。）但是存在许多实际问题，特别是如果您不知道数据会有多大。如果您确实知道这一点，或者如果您准备预先分配太多空间，然后如果您获得的数据超出该空间的容量，那么这很好，尽管您仍然需要担心保持向量的排序。
一种可能更好的方法是保留索引范围的二叉搜索树，其中 BST 的叶子指向数据的“块”（即向量）。（这本质上是一棵B+ 树。）簇可以相当大；我会说一些你希望在几分钟内收到的数据量，或者几千个条目。它们不必都是相同的大小。（B+-树的扇出通常比这小，但由于您的数据“大部分是排序的”，您应该能够使用更大的。不要让它太大；唯一的一点是减少开销并可能缓存——鞭打。）
由于您的数据“大部分已排序”，因此您可以将数据累积一段时间，将其保存在普通的有序映射中（假设您有这样的东西），甚至使用插入排序保存在向量中。当这个缓冲区变得足够大时，您可以将其作为单个块附加到主数据结构中，重新分区最后一个块以处理重叠。
如果您有理由确定您很少会得到乱序键，那么将保留第二个常规 BST 乱序数据元素。任何不能通过重新分区新的块和前一个最后一个块来容纳的元素都可以添加到这个 BST 中。要进行查找，您需要在主结构和无序结构之间进行并行查找。
如果您偏执或对无序数据的数量不够确定，只需使用标准的 B+-tree 插入算法，该算法包括创建具有一点保留但未使用空间的块以允许插入（百分之几；您想避免空间开销），并在必要时拆分一个块。
于 2012-10-13T18:15:32.240 回答