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 条评论
登录 后参与评论

相关文章

来自专栏IT派

PyTorch和Tensorflow版本更新点

导语:今天为大家带来最近更新的Pytorch的更新点介绍,另外,小编Tom邀请你一起搞事情!,源代码可以扫描二维码进群找小编获取哦~ Tensorflow 主...

51550
来自专栏专知

【干货】使用TensorFlow官方Java API调用TensorFlow模型(附代码)

2.1K40
来自专栏听雨堂

Pandas对行情数据的预处理

库里是过去抓取的行情数据,间隔6秒,每分钟8-10个数据不等,还有开盘前后的一些数据,用Pandas可以更加优雅地进行处理。 ? 需要把当前时间设置为index...

232100
来自专栏三十课

基于规则评分的密码强度检测算法分析及实现(JavaScript)

用正则表达式做用户密码强度的通过性判定,过于简单粗暴,不但用户体验差,而且用户帐号安全性也差。那么如何准确评价用户密码的强度,保护用户帐号安全呢?本文分析介绍了...

61860
来自专栏落影的专栏

GPUImage详细解析

从源码的角度分析、学习GPUImage和OpenGL ES,这是第一篇,介绍GPUImageFilter 和 GPUImageFramebuffer。 Open...

36160
来自专栏程序人生

那些年,我追过的绘图语言(续)

自从上一篇文章发布后,大家给我推荐了不少绘图工具,比如startUML,rose,TikZ package,flowchart.js,matlab,R等等。感兴...

41650
来自专栏小狼的世界

使用Numpy验证Google GRE的随机选择算法

最近在读《SRE Google运维解密》第20章提到数据中心内部服务器的负载均衡方法,文章对比了几种负载均衡的算法,其中随机选择算法,非常适合用 Numpy 模...

13520
来自专栏青玉伏案

算法与数据结构(六) 迪杰斯特拉算法的最短路径(Swift版)

上篇博客我们详细的介绍了两种经典的最小生成树的算法,本篇博客我们就来详细的讲一下最短路径的经典算法----迪杰斯特拉算法。首先我们先聊一下什么是最短路径,这个还...

28450
来自专栏恰童鞋骚年

设计模式的征途—8.桥接(Bridge)模式

在现实生活中,我们常常会用到两种或多种类型的笔,比如毛笔和蜡笔。假设我们需要大、中、小三种类型的画笔来绘制12中不同的颜色,如果我们使用蜡笔,需要准备3*12=...

15230
来自专栏腾讯AlloyTeam的专栏

png的故事:获取图片信息和像素内容

现在时富媒体时代,图片的重要性对于数十亿互联网用户来说不言而喻,图片本身就是像素点阵的合集,但是为了如何更快更好的存储图片而诞生了各种各样的图片格式:jpeg、...

1.9K00

扫码关注云+社区

领取腾讯云代金券