在压缩数据进行检索-SuccinctStore解析
- 动机
- 当今数据库实现Secondary Index的方式主要包括列族和建立索引两种方式。前者对于空间非常高效，但是当数据量达到一定规模后，检索性能会有开始下降。而后者虽然能够狠高效的检索，却可能会需要付出额外的存储空间，最后可能只能store在外存，无法很好的利用memory，虽然索引也可以选择一些前缀压缩的方式，但是也带来了其他问题。
- 如果能够将数据进行压缩后直接进行检索，那么我们就能把更多的数据放在memory中，关键是这种技术真的存在么？
- 答案是肯定的，这种技术叫做Succinct Data Structure，虽然我觉得称为技术有点不太对，因为这本质上是一种更加省空间的数据结构的实现方式。并且能达到Self-Indexing（数据就是索引）的效果。这部分的内容MIT的Advanced Data Structures有提及，对这部分感兴趣的同学可以去看看。
- 设计选择
- 我选择了Succinct Suffix Array来实现整个数据库存储引擎。
- 通过引入NPA(Next Position Array)来减少对于SA，ISA等其他存储的需要。这些后面我会有机会会介绍。
- 正则表达式的支持是我目前在努力实现的下一部分功能。
- 目标
- 通过SuccinctStore提供的高效检索实现，实现一个减量不减质的缩水版lucene，构建一个单机上性能较高的搜索引擎。预期应该会比其他同类型的实现快上许多:)
- 缺陷
- SuccinctStore的实现会导致顺序读的性能有些折扣，它更加适合随机读多的场景。