User:Drmingdrmer/沙盒

SlimTrie 类似于Trie, 是一种有序的树，用于索引关联数组，其中的键通常是字符串。 SlimTrie与Trie的不同之处在于, 它不保存完整键的信息, 而只保存用于定位一个键的关键信息, 因此SlimTrie具有的内存占用非常低, 对每个键平均占用6个byte。

应用场景

• 静态数据索引

数据生成之后在使用阶段不修改, 依赖于这个假设我们可以对索引进行更多的优化: 预先对所有的key进行扫描, 提取特征, 大大降低索引信息的量。 在存储系统中, 需要被索引的数据大部分是静态的: 数据的更新是通过Append 和 Compact这2个操作完成的. 一般不需要随机插入一条记录.

• SlimTrie保证存在的key被正确的定位

只对存在的key给出正确返回。对于不存在的key不保证返回的结果正确，可能直接返回没被定位到，也可能返回一个存储存在的key的信息，这样的设计是为了可以去掉更多与定位一个key无关的信息。

• 允许被索引到的key不一定存在

索引的目的在于快速定位一个对象, 但不保证定位到的对象一定存在，就像Btree的中间节点, 用来确定key的范围, 但要查找的key是否真的存在, 需要在Btree的叶子节点(真实数据)上来确定。

• SlimTrie支持顺序遍历存在的key

索引很多情况下需要支持范围查询，SlimTrie 作为索引的数据结构，一定是支持顺序遍历的特点。SlimTrie 在结构上与树形结构有相似点，顺序遍历的实现并不难。

• SlimTrie的内存开销只与key的个数n相关，不依赖于key的长度k.

• SlimTrie支持最大16KB的key.

• SlimTrie查询速度要快.

术语

• n: key的总数: 1 - 2^32
• k: key的平均长度 1 - 2^16
• k[i]: 某个key的长度 1 - 2^16
• userdata: 要索引的用户数据, 这里userdata是一组(offset, size)
• leaf: SlimTrie中的叶子节点, 每个leaf对应一个存在的key
• inner: SlimTrie中的非叶子节点

算法

SlimTrie的生成分为三部分。

• 先用一个Trie来做所有key的索引, 并在Trie的基础上做裁剪, 将索引数据的量级从O(n * k)降低到O(n)。
• Trie的压缩, 通过一个compacted array来存储整个Trie的数据结构, 在实现上将内存开销降低。
• 对小文件的优化, 将多个相邻的小文件用1条索引来标识, 平衡IO开销和内存开销。

中间节点剪裁

将标准SlimTrie作为索引使用的时候, 不需要对每个branch都进行保存，因为我们只需要满足设计目标1和目标2，因此在索引层只负责让存在的key可以被定位到, 不存在的key在数据层反馈。 基于以上设计，可以意识到：多分支的SlimTrie节点是关键的，单分支的节点对定位一个存在的key没有任何帮助。所以可以裁剪掉单分支节点。

叶子节点剪裁

上图中abdfg中的g节点不需要保留, 因为合法key的前缀如果是abdf, 它最后1个字符只能是g，abdfg的g去掉, 同理，b123中的3去掉, 于是裁剪之后的结果:

压缩数组

使用压缩数组来保存SlimTrie的逻辑结构, 压缩数组用来保存最大大小不超过65536 个条目的信息，首先定义压缩数组的结构：

4bit word

将全量数据拆分成较小的组, 每个组内使用SlimTrie索引, 再通过id来替代指针(16bit id)，组间使用标准的SlimTrie索引，即对索引进行分层。 将1个8bit的byte拆分成2个4bit的word作为SlimTrie上节点的单位. 这样可以有效减少bitmap在使用时额外的内存开销。

时间空间效率分析

• 
  Caption1
• 
  Caption2

外部链接

• SlimTrie at github