阿里云「飞天发布时刻」2024来啦!新产品、新特性、新能力、新方案,等你来探~ 了解详情
写点什么

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

  • 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:3311619

评论 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
回复
没有更多了
发现更多内容

抖音快手短视频获客软件开发系统

棒极了!可以让你Java程序快上180%以上的阿里性能优化笔记

Java架构追梦

Java 阿里巴巴 架构 面试 性能优化

还在使用NoSQL数据库?为IoT选择TSDB

数据库 大数据 时序数据库 tsdb 数据智能

多鲸资本发布《2021教育实时音视频行业报告》:拍乐云以质取胜做行业引领者

拍乐云Pano

6月热点:BML全新升级WebIDE编程环境,度目智能视频分析盒G1上新

百度大脑

人工智能 BML

区块链不是一个风口,而是一个时代

CECBC

实战-使用 SSM 工具创建可动态扩容的存储池

学神来啦

Linux 运维 ssm Linux教程

《人这一辈子,都在为认知闭环买单》读后感---刘润

Changing Lin

网络研讨会|为什么在开发流程中应用静态代码分析工具?

鉴释

在线研讨会 静态代码分析

从 Web 图标演进历史看最佳实践

百度Geek说

大前端

揭秘Hologres如何支持超高QPS在线服务(点查)场景

阿里云大数据AI技术

解决智慧城市发展困扰:Web3D智慧环卫GIS系统

一只数据鲸鱼

GIS 数据可视化 智慧城市 智慧环卫

【等保知识】等保测评机构申请条件,所需资料以及流程

行云管家

等保 堡垒机 行云管家 等保测评

启动、内存、卡顿三大分析,用户体验就用它?

App

Chaos Mesh 助力 Apache APISIX 提升稳定性

API7.ai 技术团队

lua 网关 APISIX Chaos Mesh

丰富 TF Serving 生态,爱奇艺开源灵活高性能的推理系统 XGBoost Serving

爱奇艺技术产品团队

开源 优化 tensorflow serving 推理

存储大师班 | NFS 的诞生与成长

QingStor分布式存储

分布式存储 分布式文件存储 NAS NFS

细节分析Linux中五种IO模型和三种实现方式

Linux服务器开发

网络编程 epoll Linux服务器开发 Linux后台开发 IO模型

kafka日志存储以及清理机制

泽睿

kafak

数字人民币如何普惠百姓?建行发布新金融数字便民计划

CECBC

Jar 组件自动化风险监测和升级实践

Qunar技术沙龙

安全 风险管理

可以同时管理公有云和私有云资源的软件哪个好?

行云管家

公有云 私有云 云管平台 云资源

记一次真实的JVM性能调优过程

北游学Java

Java JVM 性能调优

模块三作业

燕燕 yen yen

架构训练营

又一数据库高危漏洞爆出,数据安全如何有效保障?

华为云开发者联盟

redis 漏洞 GaussDB(for Redis) 开源Redis 数据库安全

上架一夜遭全网封杀!阿里大牛熬夜半年手码的Java面试指南太强了

白亦杨

Java 编程 程序员 架构师

技术解码 | 腾讯云SRT弱网优化

腾讯云音视频

百度AI寻人获评《新周刊》2021年度公益项目

百度大脑

人工智能 寻人

Ipfs国家认可吗?国家对ipfs区块链是什么政策?

区块链 分布式存储 IPFS fil

从零开始学习3D可视化之数据对接(3)

ThingJS数字孪生引擎

大前端 数据 物联网 可视化 数字孪生

Android Flutter 多实例实践

网易云信

flutter 架构

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