内存

SlimTrie: 单机百亿文件的极致索引-实现篇

2019-03-12 · 李文博(wenbo), 吴义谱(pengsven), Zhang Yanpo (drdr.xp)

SlimTrie的代码级实现详解：通过Trie裁剪去除单分支节点将空间从O(n*k)降至O(n)，再用compacted array压缩存储，最终每条索引仅需约6字节（加4字节value共10字节）。实测内存开销约为B-Tree的13%，查询速度约为其2.6倍。

2018-07-30 · 李文博(wenbo), 吴义谱(pengsven), Zhang Yanpo (drdr.xp)

单机100TB存储如何索引百亿小文件？经典的hash map和B-Tree索引的内存开销为O(k*n)，无法全部放入内存。SlimTrie基于Trie裁剪和压缩，将空间复杂度降至O(n)，实现每条索引仅约10字节，在1GB内存中即可建立100TB数据量的索引。