0

我有一个带有一些排序数据的文本文件，用换行符分割。例如：

...
abc123
abc124
abd123
abd124
abd125
...

现在我想为数据集创建一个索引，它应该（至少）支持：

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

  2. getIndexByString(s)：在所有项目中查找 s，返回其索引（如果未找到，则返回 -1）；

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

4

1 回答 1

2

由于数据已排序，因此您只需在内存中保留一小部分数据，就可以非常快速有效地定位内容。例如，假设我们决定将每个第 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 调用的开销最痛。

于 2013-04-05T04:03:02.590 回答