【QCon】精华内容上线92%,全面覆盖“人工智能+”的典型案例!>>> 了解详情
写点什么

数据库内核杂谈(三):索引优化

  • 2019-12-13
  • 本文字数:4984 字

    阅读完需:约 16 分钟

数据库内核杂谈(三):索引优化

本篇文章选自数据库内核杂谈系列文章。


在上一篇文章的末尾,我们留了一个坑。虽然通过列存,能够避免读取不必要的数据(没使用的列)来提高查询速度,但是对于下面这类点查询(point query),还能不能进一步优化呢?


SELECT * FROM titanic_survivor WHERE age = 10;
复制代码


答案是肯定的,解决方案就是今天的主题 – 索引(index)。


索引这个概念在我们日常生活中很常见。比如在很多书籍的最后,都配有关键字索引。它能帮助你快速地找到某个关键字所在的书页。试想一下,如果没有索引,想要查询某个关键字所在的章节和书页,可能唯一的办法就是一页一页翻书直到找到为止。索引大大提高了查询的速度!


数据库的索引也正是为了解决这类问题:索引通过引入冗余的数据存储(类比书籍最后的索引章节),以此来提高查询语句的速度。和上一期的结构类似,相较于列举不同索引类型的分类法,我们依然从解决问题的角度来看不同类型的索引是为了解决哪些查询而演化而来的。


回到上面这个点查询语句,你能想到什么办法来优化执行?我们沿用上一期 titanic_survivor 的数据(下图),一起来看。



titanic_survivor


读者可能很容易就会想到,我们可以建立一个哈希表(HashMap)。哈希表的键(key)存储 age 的值,哈希表的值(value)存储所有 age 为对应键值的 row 在存储系统中的相对位置(如果使用 csv 文件存储,它就是 row 的行号。如果用字节流存储数据,它就是 row 对应于文件中的 offset)。下图是对于 titanic_survovior 的 age 列作索引。



hash_table_age


有了这样一个哈希表,当需要查询年龄是 35 的幸存者时,只需要读取行 4 和行 5 的数据即可。(可能对于 csv 文件比较难描述这类优化。设想当数据文件是按字节流存储时,可以用随机文件读取的 API 来读取很小一部分数据) 虽然随机读取的平均效率远低于顺序读取(因为文件系统需要寻道 seek),但相比于读取 2 行数据和一百万行数据,前者的速度毋庸置疑得快。


这样一个哈希表,就引出了第一类索引,哈希索引(Hash Index): 根据需要索引的列(并不限制为一个列,可以是多个列的组合),建立一个哈希表。读取数据时,先根据索引列的键值找到对应的数据位置,然后读取相应数据。


本文不是数据结构 101,就不具体讨论如何实现哈希函数,解决键冲突,对哈希表进行扩容缩容等的问题了。稍微聊一些工程实践中的细节:选择哈希函数的指标,肯定是速度越快越好。在输入和输出值域相同的情况下,冲突概率越低越好。下面列举了一些开源且受欢迎的哈希函数实现,有兴趣的同学可以深入学习:


  1. MurmurHash (2008):

  2. https://en.wikipedia.org/wiki/MurmurHash

  3. Google CityHash (2011):

  4. https://opensource.googleblog.com/2011/04/introducing-cityhash.html

  5. Google FarmHash (2014):

  6. https://opensource.googleblog.com/2014/03/introducing-farmhash.html

  7. CLHash (Carry-less) (2016):

  8. https://arxiv.org/abs/1503.03465


有同学提出疑问,提到哈希算法, 最先想到的就是 MD5, SHA 等的算法,为什么这里并没有提及。因为这类算法被称为密码哈希算法(当然 MD5 已经多次被证明不安全了,请不要继续用于加密。。)。为了追求安全性,这类算法具备特别的属性,比如难以从一个已知的哈希值去逆推原始的消息以及雪崩效应(Avalanche effect): 即输入发生微小变化也会导致输出的不可区分性改变,从而牺牲了哈希运算的效率。建立哈希索引时并不需要这类安全属性,因此会选择性能更高的哈希算法。


著名的开源数据库 PostgreSQL 就支持哈希索引,生成语句如下:


(CREATE INDEX index_name ON table_name USING HASH (column_name);
复制代码


但在对应的文档中,却明确指出了不建议使用哈希索引。至于原因,我们先卖个关子,过一会再详解。总结一下,为了提高点查询的效率,我们引入了第一类索引,哈希索引。


哈希索引虽好,却也不是万能的。比如把查询条件从点查询改为范围查询,如下所示:


SELECT * FROM titanic_survivor WHERE age BETWEEN 1 AND 10;
复制代码


有同学说,依然可以用哈希索引解决,只要做 10 次哈希索引的查询即可。那我做得再绝一些:


SELECT * FROM titanic_survivor WHERE age > 10;
复制代码


或者干脆把 age 换成浮点类型。如此,哈希索引是万万没辙了吧。


面对这类查询,有什么方法可以提高速度呢?有读者会想到,如果把要查询的列(此为 age)进行排序,然后进行二分查找来定位,依次扫描列中满足条件的数据,就可以避免全文件扫描了。沿用上面的示例,我们对 titanic_survivor 的 age 列排序,并且纪录相应的行号, 如下图所示:



sorted_age_list


假设需要查询年龄在 20 至 40 岁之间的幸存者,可以通过二分查找先定位到年龄 22,然后依次顺序读取之后 26,35 和 38 岁的对应行的数据,当搜索至 54 岁时停止即可。概括一下方法:对相关列进行排序,用二分查找来快速定位然后顺序查询。二分查找 1 至 100 万中的某个数需要 20 次查询(2^20 约等于 100 万),有什么方法可以再进一步提高效率?于是我们引出第二个使用的数据结构 B 树和 B+树(B - tree, B+ - Tree)。


关于 B 树和 B+树的具体实现细节,请参考相关数据结构书籍资料,这里就不赘述了。简单而言,B 树相当于把二分查找变成了 N 分查找,假设 N 为 100,那查找范围为(1, 100 万)就只需要 3 次分叉了(100^3 = 100 万)。B+树和 B 树的区别就在于 B 树在非叶节点也会存储数据而 B+树仅在页节点存储数据。下图示例为 B+树。



B+ tree


这类索引就称之为 B 树索引。B 树和 B+树通过引入有很多分枝的树节点来提高定位速度以此来提高整体查询速度,算得上是空间换时间的方法。同样,在工程中还有很多可优化的细节。比如对于 B+树,只有页节点存储具体的数据信息,内节点和根节点仅仅是用于快速定位,因此衍生出了合并前缀(prefix compression)以及删除无用后缀(suffix truncation)等的优化方法。再举个常见的优化示例,B+树的页节点原本用来存储对应列值的行在数据文件中的相对位置,所以读取完索引后还需要根据相对位置去数据文件中读取数据。但对于固定的查询语句,可以提前知道其他哪些列也会经常被查询,把这些列的数据直接存储在索引中,进一步用空间来省去读取数据文件的时间。比如,如果我们想要更进一步优化下面这个语句:


SELECT sex FROM titanic_survivor WHERE age > 10;
复制代码


就可以把性别的信息存放在索引中。对应的 SQL 语句如下


CREATE INDEX btree_idx_age ON titanic_survivor(age) USING BTREE INCLUDE (sex);
复制代码


为了能够进一步优化范围查询,我们引出了第二类索引,B 树索引。现在可以聊聊上面埋下的伏笔为什么 Postgres 并不建议使用哈希索引了。贴出原文(From Postgres 7.2 Doc):


Because of the limited utility of hash indexes, a B-tree index should generally be preferred over a hash index. We do not have sufficient evidence that hash indexes are actually faster than B-trees even for = comparisons. Moreover, hash indexes require coarser locks.


可见,虽然从理论上讲,对于点查询,哈希索引应该更快,而且存储空间相对 B 树索引更少。但是通过工程中的优化,可以让 B 树索引在点查询中也毫不逊色。聊完了哈希索引和 B 树索引,留一个思考题给读者:抛开性能不说,用 B 树索引读取数据还能带来一个隐形的好处,猜猜是什么好处?我会把答案留在本文的最后。


说了这么多 B 树索引的优势,它有什么缺陷吗?B 树的实现,增加和删除数据会牵涉到节点的分离和合并,是比较复杂的(没有同学在面试过程中遇到要求实现 B 树这类的变态问题吧)。尤其是在高并发的环境下,对于节点的操作需要加锁, 会进一步导致速度变慢。有没有办法进一步改进吗?有!有一种比较偏门的数据结构 – 跳表(skip list)比 B 树在这方面就更优秀。跳表的实现是一个多层次的链表,底部链表和 B 树一样是一列有序的键值对,通过在上层加入更松散的有序链表来支持跳跃查询(命名的由来)。下图给出了跳表示例。



skip list


理论上的时间复杂度和 B 树是类似的。但为什么说跳表对于高并发更好呢,我自己的理解是因为在新增节点时,跳表通过一个概率值来决定是否需要添加上层节点,实现起来,变化比较局部,不会有 B 树那样牵一发而动全身的变化,所以无论是加锁实现,还是无锁实现都对高并发支持更好。如果想要了解更多,请各位同学自行查阅。跳表的另一个优势在于实现中对于内存的需求相对于 B 树更少。可能这也是为什么内存数据库 MemSql 就支持跳表索引。其实跳表也有缺点,因为是用链表实现,所以对于缓存并不是很友好。另一个缺点是,要支持逆向查询,比如(age < 40),这就需要用双向链表实现,复杂度也会更高。


总结一下,为了更好得支持并发操作以及内存优化,我们引入了跳表索引。


B 树索引还有哪些情况是不适用的吗?现在假设我们要对性别或者舱位做索引,但这些列本来基数(distinct value cardinality)就非常小,B 树带来的快速定位优势就没有意义了。有什么索引是适合这类查询吗?引出我们今天最后的一类索引 – 位图索引。


位图索引专门针对基数很小的列来做索引。比如对于性别,我们可以生成下列的索引:



sex bitmap index


SELECT * FROM titanic_survivor WHERE sex = 'female' AND cabin = 'A'
复制代码


我们可以同时对 sex 和 cabin 做位图索引,然后对 sex:female 和 cabin:A 进行位图与操作再读取结果为 1 的行即可。除此之外,位图索引的另一大优势在于,相对于其他索引,存储需求很小:对于每个基数,每一行数据只要 1bit 的存储。所以当列的基数很大时,位图索引就失去意义了。位图索引的另一个劣势在于,不适用于高并发环境,因为任何修改和添加,都需要对索引文件进行加锁。


针对基数较小的列,我们引入了位图索引来提高查询速度。

小结

数据库索引是用来进一步提高查询语句的速度。针对不同的数据环境和不同索引的优缺点,我们介绍了以下这些方法:


1) 引入哈希索引用来提高点查询效率


2) 引入 B 树索引用来提高范围查询


3) 针对 B 树索引对高并发支持的诟病,引入跳表索引


4) 针对基数较小的列,引入位图索引


使用索引时,可以对每个表创建一个或多个索引。读者可能会有疑问,那岂不是对每个列都创建索引,就是万事大吉了。答案是否定的。索引是否能够提升效率,取决于查询语句以及数据的分布。而是否决定使用索引,是由数据库的优化器(之后会有专门的章节介绍优化器)决定的。另外,天下没有免费的午餐。首先,索引是冗余的数据存储,是要占据内存和磁盘空间的。二,索引数据要和表数据同步,在对修改数据的同时,也需要同步更新索引。如果索引太多,会大大降低数据导入和修改的吞吐量(可以在 Postgres 中做小实验,在有和没有索引的情况下,导入数据的时间相差甚远)。工程实践中,一般会在数据更新操作全部完成以后,再对表建索引。如何正确创建的索引,是原先 DBA 的工作;一个有经验的 DBA,能够根据查询需求创建最高效的索引。在越来越智能的数据库时代,很多数据库已经可以根据查询语句的类型,来提供创建索引的建议,毕竟没有数据库比数据库本身更懂自己!


下面揭露思考题答案:用 B 树索引读取数据的另一个好处是什么?那就是读取的数据针对索引列是排过序的。这可是一个非常好的特性,假设查询语句中本来就有排序需求(SQL 关键字 ORDER BY), 就不用再对数据进行排序了。另外有序列对于数据表的联合(join),以及聚类(aggregation)都很有帮助,这些我们留到以后再介绍。


作者介绍:


顾仲贤,现任 Facebook Tech Lead,专注于数据库,分布式系统,数据密集型应用后端架构与开发。拥有多年分布式数据库内核开发经验,发表数十篇数据库顶级期刊并申请获得多项专利,对搜索,即时通讯系统有深刻理解,爱设计爱架构,持续跟进互联网前沿技术。


2008 年毕业于上海交大软件学院,2012 年,获得美国加州大学戴维斯计算机硕士,博士学位;2013-2014 年任 Pivotal 数据库核心研发团队资深工程师,开发开源数据库优化器 Orca;2016 年作为初创员工加入 Datometry,任首席工程师,负责全球首家数据库虚拟化平台开发;2017 年至今就职于 Facebook 任 Tech Lead,领导重构搜索相关后端服务及数据管道, 管理即时通讯软件 WhatsApp 数据平台负责数据收集,整理,并提供后续应用。


相关阅读:


数据库内核杂谈(一):一小时实现一个基本功能的数据库


数据库内核杂谈(二):存储“演化论”


2019-12-13 14:3311556

评论 10 条评论

发布
用户头像
基数小的列的位图索引的cardinality值会不会很大呢?如果利用索引读取不是会有很多随机IO吗?
2022-01-17 18:41
回复
用户头像
作者留言:2022年1月1日,祝大家新年快乐。不知不觉,数据库内核杂谈又陪伴大家一年(虽然。。还是不可避免地拖更了)。今年的new year resolution,希望创建一个群,和大家一起交流。加我微信 81211430(请备注数据库内核杂谈,谢谢),我会建群。期待和大家交流。
2022-01-01 12:28
回复
用户头像
B树和跳表不是一个维度的比较吧?B树主要利用局部性原理,一次读取一个页。叶子节点一次存储一个页数据。跳表是一个存内存数据结构。两者不是一个维度的东西。
2021-09-13 10:18
回复
解决数据库访问时锁表频率具有意义
2022-06-02 11:30
回复
用户头像
精辟

B 树相当于把二分查找变成了 N 分查找

2021-02-21 22:49
回复
用户头像
"B 树相当于把二分查找变成了 N 分查找" 精辟
2021-02-21 22:34
回复
用户头像
大佬,您好,我有个问题想问下:用B+树创建聚集索引,数据都是存储在叶节点上,数据间用双向链表关联,但是因为数据文件是append only的,这样就会导致双向链表的逻辑顺序和磁盘上的存储顺序不一致,应该会大大降低读取速度吧。(这个有什么办法优化吗?)
2021-02-20 10:20
回复
一般可以使用预取(预读)来将随机读转化为顺序读,每次读取的并不是查询页 的数据,连查询它相连的下面的页页查询出来
2021-08-16 16:57
回复
用户头像
作者来留个言,一言难尽的2020终于过去了,新年快乐,希望2021对所有人,都充满惊喜。数据库内核杂谈也已经更新到第十四期了,再次感谢各位的关注。如果你是内核杂谈的真粉丝,觉得内核杂谈对你有收获,愿意听我多扯扯,欢迎加入我的知识星球:Dr.ZZZ 聊技术和管理:https://t.zsxq.com/VrZbeAE(由于不知道能输出多少,也不知道有多少粉丝,所以还是先免费吧)
2021-01-01 02:35
回复
该评论已删除
2021-02-04 14:48
回复
用户头像
B树 B+树 跳表 位图索引 B树天然有序对order by支持较好
2019-12-18 17:43
回复
没有更多了
发现更多内容

react源码中的fiber架构

flyzz177

React

ElasticSearch必知必会-基础篇

京东科技开发者

大数据 搜索引擎 数据分析 技术分享 Elastic Search

精准测试之覆盖

京东科技开发者

数据库 测试 代码 覆盖 企业号 1 月 PK 榜

Diffie-Hellman密钥协商算法探究

百度Geek说

数据安全 企业号 1 月 PK 榜

华为云Stack新版发布:构筑行业云底座,共创行业新价值

华为云开发者联盟

云计算 后端 华为云 企业号 1 月 PK 榜

软件测试/测试开发 | AppCrawler 自动遍历测试工具实践(一)

测试人

软件测试 自动化测试 测试开发 自动遍历 AppCrawler

如何使用 Towify 在小程序中创建关联表?

Towify

HDI压合设计准则作业规范

华秋PCB

PCB PCB设计 HDI

编程的终结;展望2023年AI系统方向;AI的下一个阶段

OneFlow

人工智能 深度学习

总有一个你能用上的29个IDEA小技巧

风铃架构日知录

Java 程序员 IDEA IT 开发工具

硬实力,高潜力!旺链科技当选“2022德勤中国高科技高成长50强”

旺链科技

区块链 区块链技术

网页抓取中最常用的三大 Python 库

Geek_2d6073

3700万人在线见证梅西“圆梦”!火山引擎实力护航世界杯

火山引擎边缘云

云计算 云原生 CDN 边缘计算 火山引擎边缘计算

GitHub上标星79K的LeetCode算法小抄开放下载了

小小怪下士

程序员 面试 算法 LeetCode

牛啊!长这么大还是头一次见24W字的SpringBoot从入门到实战文档

程序知音

Java spring 微服务 springboot 后端技术

火山引擎 DataLeap 通过中国信通院测评,数据管理能力获官方认可!

字节跳动数据平台

大数据 数据治理

文末领资料 | 研发效能领域的三个年度关键词

思码逸研发效能

研发管理 研发效能

【等保小知识】等保3.0就是等保三级吗?

行云管家

等保 等保2.0 等保3.0

react源码中的hooks

flyzz177

React

要避免的自动化实践

FunTester

创建好的小程序如何正式发布?

Towify

【等保小知识】等保四级是最高级别吗?等保四级适用于哪些领域?

行云管家

等保 等保测评 等保四级

数字图像处理笔记

嵌入式视觉

数字图像处理 几何变换 低通滤波 图像锐化 高通滤波

学术加油站|机器学习应用在数据库调优领域的前沿工作解读

OceanBase 数据库

数据库 oceanbase

【Redis 技术探索】「数据迁移实战」手把手教你如何实现在线 + 离线模式进行迁移 Redis 数据实战指南(数据检查对比)

洛神灬殇

redis 1月日更 数据对比 Redis-full-check

无监控,不运维!深入浅出介绍ChengYing监控设计和使用

袋鼠云数栈

TDengine 公布 2022 年度中国时序数据应用创新奖,33 个科技企业创新应用脱颖而出

TDengine

数据库 tdengine 时序数据库

开源共建|旺链科技与FISCO BCOS达成产业应用合作

旺链科技

区块链 开源 区块链技术

一文总结ACE代码框架

OpenHarmony开发者

OpenHarmony

大咖说·对话开源|与Tapdata论道数据技术开放生态

大咖说

开源

react hook 源码完全解读

flyzz177

React

数据库内核杂谈(三):索引优化_数据库_顾仲贤_InfoQ精选文章