Succinct Data Structure

作者:唐刘

最近看了一篇论文 SuRF: Practical Range Query Filtering with Fast Succinct Tries,里面提到使用一种新的数据结构 Succinct Range Filter(SuRF) 替换掉了 RocksDB 默认的 Bloom filter, 在一些性能测试上面,尤其是 seek 上面,性能提升了不少,并且也降低了很多 I/O 开销,这一下子就引起了我的兴趣。

大家都知道,RocksDB 里面,为了加速 key 查询的速度,使用了 Bloom filter,但 Bloom filter 只适用于 point get,对于 seek 就无能为力了。虽然 RocksDB 后面引入了 prefix seek,但对于 key 的格式有要求,使用比较受限。为了提高 RocksDB range query 的速度,论文的作者引入了一种省空间的数据结构,也就是 SuRF。

在了解 SuRF 之前,首先要了解掌握的就是 Succinct data structure 相关的知识,这篇文章主要是讲 Succinct data structure 相关的东西,后面再讨论 SuRF 如何实现的。

Rank 和 Select

Succinct data structure 第一次提出,应该是 Guy Jacobson 的论文 "Succinct static data structures",但实话,我在网上找了半天,都没找到这篇 paper,只是找到了作者另一篇 Space-efficient static trees and graphs。它的主要思想就是使用非常少量的空间(接近信息编码的下界)来存储数据。你可以认为就是使用了一种非常高效的压缩算法,但不同于压缩,它同时来提供非常高效的查询。

对于 Succinct data structure 来说,我们会将数据按 0 和 1 来编码,所以可以用 bits,而不是 bytes。操作 succinct 数据,通常的就是几个操作函数:

  • rank1(x) - 返回在 range [0, x]里面 1 的个数
  • select1(y) - 返回第 y 个 1 所在的位置

上面我们只是列举了 rank1 和 select1,对应的也有 rank0 和 select0,这里就不需要解释了。这么说有点过于抽象,这里举一个简单的例子。假设我们有一个 bits 序列 11000001,那么 rank1 和 select1 可以映射如下:

image

另外,大家可以注意到,rank 和 select 其实是相反的,上面的例子,select1(3) = 7,然后我们也会发现,rank1(7) = 3

Level Order Unary Degree Sequence

上面简单介绍了下 Succinct data structure 的 rank 和 select。 在 SuRF 里面,它参考的基础编码方式,是 Level order unary degree sequence(LOUDS),在 LOUDS 里面,我们会将一颗树,分层依次进行编码。而规则也是非常的简单,如果这个树的节点有 N 个子节点,那么就用 N 个 1 来编码,然后最后加上 0。

假设我们有如下的 tree:

image

为了计算简单,LOUDS 会加入一个 pseudo root 节点,这里我们变成如下的 tree:

image

然后我们对这个 tree 进行编码,得到:

image

那么生成的 bits 序列为:

image

那么我们拿到了这一个序列到底有什么用呢?在 LOUDS 里面,我们可以非常方便的进行很多操作,假设我们的 node 就是按照上面的,0,1,2,这样的 number 来标记的,position 对应的就是 bits 里面的 position。我们通常会用两个计算公式来得到 node number 和 position 的对应关系:

  • node-num = rank1(i):在 position i 得到对应的 node number,譬如 rank1(2) = 2
  • i = select1(node-num),根据 node number,知道对应的 position,譬如 select1(2) = 2

有了上面的公式,我们就能对这个 tree 进行操作了:

  • first_child(i) = select0(rank1(i)) + 1 - 得到第 i 个位置所在节点的第一个子节点所在的 position
  • last_child(i) = select0(rank1(i) + 1) - 1 - 得到第 i 个位置所在节点的最后一个子节点所在的 position
  • parent(i) = select1(rank0(i)) - 得到第 i 个位置所在节点的父节点所在的 position
  • children(i) = last_child(i) - first_child(i) + 1 - 得到第 i 个位置所在节点的子节点的个数
  • child(i, num) = first_child(i) + num 得到第 i 个位置所在节点的第 num 个子节点所在的 position,num >= 0

上面这些公式感觉好绕,那么我们来一个简单的例子,以节点 4 为例。从上面的 tree 可以知道,4 的 parent node 是 1,它的第一个子节点是 7,最后一个是 8,总共有两个子节点。

首先我们需要计算节点 4 的位置,根据上面的公式 select1(4) 我们得到 position 是 4。那么第一个子节点位置就是 first_child(4) = select0(rank1(4)) + 1 = select0(4) + 1 = 9 + 1 = 10,那么第一个子节点就是 rank1(10) = 7

我们再来计算最后一个子节点,根据公式,最后一个就是 last_child(4) = select0(rank1(4) + 1) - 1 = select0(4 + 1) - 1 = 12 - 1 = 11,那么最后一个子节点就是 rank1(11) = 8

再来看看父节点,就是 parent(4) = select1(rank0(4)) = select1(1) = 0,那么父节点就是 rank1(0) = 1

Epilogue

使用 LODUS,我们可以用 bits 方便的编码一棵树,然后用 rank 和 select 操作,就能方便的对 tree 进行遍历,业内已经有很多 paper,能将 rank 和 select 做到 O(1) 的开销,所以速度还是很快的。

但在实际中,如果光用 LODUS,性能还是没法保证的,所以这也是为啥会有 SuRF 的原因,关于 SuRF,后面会在说明。

在数据库领域,Succinct 是一个比较有趣的研究方向,也有很多数据库采用了 succinct 来保存数据,毕竟如果能用更少的空间存放数据,memory 能装的更多,cache 更友好,性能就更好。但现在 succinct 还没有大规模的落地,可以看看后续的发展。如果你对构建新的存储引擎有兴趣,欢迎联系我 tl@pingcap.com。

原文链接

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python花式编程案例锦集(3)

严格来说,本文的2个代码不算花式编程,在Python中就应该是这样写。 1、生成包含20个随机数的列表,然后删除其中的所有奇数。 from random imp...

33613
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

3285
来自专栏互联网大杂烩

Python 异常值分析

异常值分析是检验数据是否有录入错误以及含有不合常理的数据。忽视异常值的存在是十分危险的,不加剔除地把异常值包括进数据的计算分析过程中,对结果会产生不良影响;重视...

862
来自专栏take time, save time

桌面山寨版2048—游戏逻辑篇之移动方块的框架

         昨天看到博客(www.richinmemory.com)的流量统计,居然还有一位朋友评论了,感动的满眼都是泪啊!谢谢支持啊!为了使互动的朋友更...

3447
来自专栏desperate633

LintCode 不同的路径题目分析代码

有一个机器人的位于一个M×N个网格左上角(下图中标记为'Start')。 机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角(下图中标记为'F...

392
来自专栏机器之心

业界 | 探索Siri背后的技术:将逆文本标准化(ITN)转化为标签问题

2744
来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

933
来自专栏老马说编程

(34) 随机 / 计算机程序的思维逻辑

随机 本节,我们来讨论随机,随机是计算机程序中一个非常常见的需求,比如说: 各种游戏中有大量的随机,比如扑克游戏洗牌 微信抢红包,抢的红包金额是随机的 北京购...

2026
来自专栏蜉蝣禅修之道

C++简单实现八皇后问题

952
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

902

扫码关注云+社区