首页
学习
活动
专区
工具
TVP
发布

理解B+树索引以及它们如何影响性能

本文为翻译的文章,作者ovais.tariq,原文:

http://www.ovaistariq.net/733/understanding-btree-indexes-and-how-they-impact-performance/#.Wz8dxNIzZPZ

索引是数据库中非常重要的部分,经常用来加快对于特定数据项的访问。所以在使用索引之前,先搞清楚索引在幕后是如何工作的,以及用来保存索引的数据结构是什么,是很重要的,因为,除非你理解索引的内部工作机制,否则你永远不能充分利用它的能力。

B+树索

索引是以B+树数据结构的形式保存到磁盘上的。B+树在很多方面都与二叉查找树相似。B+树与二叉查找树的结构完全一样,因为对每个结点来说,左子树上所有结点的值都小于该结点的值,右子树上所有结点的值都大于该结点的值。

但也有一些重要的区别:

B+树在一个结点中可能包含多个键。事实上,一个典型的结点包含了上千个键,因此B+树的分支因子很大,与二叉查找树相比,B+树就要浅得多。

B+树把所有的值保存在叶子结点【译者注:非叶子结点只包含索引】。所有的叶子结点高度相同,这意味着每次索引查找都使用了相同次数的B+树搜索。

B+树的叶子结点都使用链表从左到右连在一起,因而叶子结点的值是有序的,范围查找就非常高效。

一棵典型的B+树

下面是一棵典型的B+树:

为什么使用B+树索

使用B+树的主要原因是速度。我们知道,内存有空间大小的限制,不是所有的数据都在内存中,因而大部分的数据都保存到磁盘上。与内存相比,磁盘要慢得多,因为它有活动部件。所以,如果在数据库中没有树形结构来进行查找,DBMS必须要在所有记录中进行顺序扫描。想象一下如果数据有10亿行,那么很明显,顺序扫描要花很长的时间。

但是有了B+树,可以把10亿个键值(指向10亿行记录的指针)保存在第3,4或者5层的高度上,所以每次对于10亿个键的搜索都进行3,4或者5次磁盘访问,大大减少了I/O次数。

选择B+树而不是其它树形结构,是因为B+树非常浅,每次查找都转换成一次磁盘访问,磁盘访问的次数与树的高度成正比,所以树越浅,磁盘访问的次数就越少。

B+树是如何组织的

B+树通常是这么组织的:根据页大小来选择结点的大小。为什么?因为访问磁盘上的数据,都是读取整页的数据,而不是读取部分数据,因为这样成本要低得多。

让我们来看个例子。

InnoDB的页大小是16KB,假定我们在一个整型字段中有一个大小为4B的索引,所以一个结点最多包含16 * 1024 / 4 = 4096个键,且最多有4097个子结点。

所以对于一个高度为1的B+树,根结点有4096个键,第一层结点(叶子结点)有4096 * 4097 = 16781312个键值。

这显示了B+树的效率,超过1600多万个键值可以被存储在B+树的第一层,因而每个键值都可以通过2次查找来获得。

索引值的大小有多重要

从前面的例子可以看出,索引值的大小扮演了非常重要的角色,因为:

索引越长,能够装进结点的数量就越少,因而B+的高度就越大

树越高,就需要越多的磁盘访问

磁盘访问的次数越多,性能越低

所以索引值的大小对于性能有直接的影响。我希望你理解B+树是怎么工作的,以及如何使用它们来提升查找的性能。我希望你能理解,让B+树的高度小一些是多么重要,因为这样就可以减少磁盘访问的次数。

原创文章,欢迎转载,但请注明出处。

欢迎大家关注本订阅号互联网全栈架构,长按下图即可。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180707G1A5MC00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券