database - 为排序后的数据创建索引

Question

我有一个包含一些排序数据的文本文件，用换行符分隔。例如:


...<br/>
abc123<br/>
abc124<br/>
abd123<br/>
abd124<br/>
abd125<br/>
...


现在我想为数据集创建一个索引，它应该(至少)支持:

1. getStringByIndex(n):返回排序列表的第n项；

2. getIndexByString(s):在所有项中查找s，返回其索引(未找到返回-1)；

我读过一些索引算法，例如散列和 B 树。具有额外子级大小字段的 B 树应该可以做到这一点。但是由于日期集已排序，我想知道是否有比通过将所有项目插入 B 树来构建 B 树更有效的解决方案？

Answer 1

由于数据已排序，您只需在内存中保留一小部分稀疏的数据子集，即可快速高效地定位内容。例如，假设我们决定将第 N 个元素存储在内存中。为了高效地初始化您的 API，您希望将这个稀疏列表编译到磁盘上的一个单独文件中，这样您就不必通过 100GB 的数据流来获取它。

对于这些术语中的每一个，您都需要保存相对于术语开始位置的文件头的磁盘偏移量。然后，您所要做的就是将稀疏列表/偏移量对加载到内存中，并且您的两个请求的实现变得简单明了:

    getStringByIndex(n):
        Get floor(n/N)-th string/offset pair from list
        Seek offset position in index
        Read/Skip n mod N strings, then return the next one

    getIndexByString(s):
        Binary search over sparse list in memory
            Locate lower and upper bound string/offset pairs
        If a string/offset pair is in the i-th position in our sparse list,
            then the string itself is the (N x i)-th string in our index.
            We can use this information to compute the return value
        If the string we want isn't in memory:
            Seek lower-bound offset in index
            Read strings until we:
                a) Find a match
                b) Reach the high-bound offset
                c) Reach a string which is lexicographically greater than the one we are looking for
        Else
            Just return the index for the matching string in our sparse list

如果索引中的字符串是固定宽度的，则可以进行更大的优化。

如果您实现此算法，您需要谨慎选择此算法的“N”。请记住，从磁盘上的一个位置读取 10 个字节的成本并不比从同一位置读取 10,000 个字节的成本低多少:这是磁盘查找的开销，以及进入和退出 I/O 调用的开销最痛。