成为VIP
本文为译文，作者ovais.tariq，原文：
索引是数据库中非常重要的部分，经常用来加快对于特定数据项的访问。所以在使用索引之前，先搞清楚索引在幕后是如何工作的，以及用来保存索引的数据结构是什么，是很重要的，因为，除非你理解索引的内部工作机制，否则你永远不能充分利用它的能力。
B+树索
索引是以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+树的高度小一些是多么重要b+树，因为这样就可以减少磁盘访问的次数。
最后推荐下面这个Java公众号，没关注的扫一波！
限时特惠：本站每日持续更新海量设计资源，一年会员只需29.9元，全站资源免费下载
站长微信：ziyuanshu688
htebazile
