理解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+树的高度小一些是多么重要，因为这样就可以减少磁盘访问的次数。

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

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