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在使用时额外的内存开销。


时间空间效率分析

编辑

参考资料

编辑

外部链接

编辑