摘要：但是目前常用的数据库中，绝大多数的索引都是使用树实现的。所以，综上所述，数据库索引使用节点大小恰好等于操作系统一页大小的树来实现是效率最高的选择。
为什么大多数数据库索引都使用B+树来实现呢？这涉及到数据结构、操作系统、计算机存储层次结构等等复杂的理论知识，但是不用担心，这篇文章20分钟之后就会给你答案。
这篇文章是一系列数据库索引文章中的最后一篇，这个系列包括了下面四篇文章：
数据库索引是什么？新华字典来帮你 —— 理解
数据库索引融会贯通 —— 深入
20分钟数据库索引设计实战 —— 实战
数据库索引为什么用B+树实现？ —— 扩展
这一系列涵盖了数据库索引从理论到实践的一系列知识，一站式解决了从理解到融会贯通的全过程，相信每一篇文章都可以给你带来更深入的体验。
为什么使用B+树？大家在数学课上一定听说过一个例子，在一堆已经排好序的数字当中找出一个特定的数字的最好办法是一种叫“二分查找”的方式。具体的过程就是先找到这些数字中间的那一个数，然后比较目标数字是大于还是小于这个数；然后根据结果继续在前一半或者后一半数字中继续查找。
这就类似于数据结构中的二叉树，二叉树就是如下的一种结构，树中的每个节点至多可以有两个子节点，而B+树每个节点则可以有N个子节点。
这里就不具体展开讲解二叉树了，我们只需要知道，平衡的二叉树是内存中查询效率最高的一种数据结构就可以了。
但是目前常用的数据库中，绝大多数的索引都是使用B+树实现的。那么为什么明明是二叉树查询效率最高，数据库中却偏偏要使用B+树而不是二叉树来实现索引呢？
计算机存储层次结构计算机中的存储结构分为好几个部分，从上到下大致可以分为寄存器、高速缓存、主存储器、辅助存储器。其中主存储器，也就是我们常说的内存；辅助存储器也被称为外存，比较常见的就是磁盘、SSD，可以用来保存文件。在这个存储结构中，每一级存储的速度都比上一级慢很多，所以程序访问越上层存储中的数据，速度就会越快。
有过编程经验的小伙伴都知道，程序运行过程中操作的基本都是内存，对外存中数据的访问往往需要写一些文件的读取和写入代码才能实现。这正是因为CPU的计算速度比存储的I/O速度（输入/输出速度）快很多所做的优化，因为CPU在每次计算完成之后就需要等待下一批的数据进入，这个等待的时间越短，计算机运行得越快。
所以对于数据库索引来说，因为数据量很大，所以基本都是保存在外存中的，这样的话数据库读取一个索引节点的成本就非常大了。在数据量一样大的情况下，我们可以知道，B+树的单个节点中包含的值个数越多那么树中需要的节点总数就会越少，这样查询一次数据需要访问的节点数就更少了。
如果你对B+树还不熟悉，可以到这篇文章中找到答案——数据库索引融会贯通 。
如果我们把二叉树看做是特殊的B+树（每个节点只有一个值和前后两个指针的B+树），那么就可以得出结论：因为B+树的节点中包含的值个数（多个值）比二叉树（1个值）更多，所以在B+树中查询所需要的节点数就更少。那么如果每次读取的成本是一样的话，因为总成本=读取次数*单次读取成本，我们就可以证明B+树的查询成本就比二叉树小得多了。
节点读取成本但是我们知道，读取更多数据肯定会需要更大的成本，那么为什么数据库索引使用B+树还是会比二叉树更好呢？这就需要一些更高深的操作系统知识来解释了。
在现代的操作系统中，把数据从外存读到内存所使用的单位一般被称为“页”，每次读取数据都需要读入整数个的“页”，而不能读入半页或者0.8页。一页的大小由操作系统决定，常见的页大小一般为4KB=4096字节。所以不管我们是要读取1字节还是2KB，最后都是需要读入一个完整的4KB大小的页的，那么一个节点的读取成本就取决于需要读入的页数。
在这样的情况下，如果一个节点的大小小于一页的大小，那么就会有一部分时间花在读取我们根本不需要的数据上（节点之外的数据），二叉树在这方面就会浪费很多时间；而如果一个节点的大小大于一页，哪怕是一页的整数倍，那我们也可能在一个节点的中间就找到了我们需要的指针进入了下一级的节点，这样这个指针后面的数据都白白读取了，如果不需要这些数据可能我们就可以少读几页了。
所以，综上所述，数据库索引使用节点大小恰好等于操作系统一页大小的B+树来实现是效率最高的选择。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/32362.html
摘要：但是目前常用的数据库中，绝大多数的索引都是使用树实现的。所以，综上所述，数据库索引使用节点大小恰好等于操作系统一页大小的树来实现是效率最高的选择。 为什么大多数数据库索引都使用B+树来实现呢？这涉及到数据结构、操作系统、计算机存储层次结构等等复杂的理论知识，但是不用担心，这篇文章20分钟之后就会给你答案。 这篇文章是一系列数据库索引文章中的最后一篇，这个系列包括了下面四篇文章： 数...
摘要：以后，可以通过参数设置当前实例下每个索引页的大小，一旦设定，无法再更改回来。因为更新表时，不仅要保存数据，还要保存一下索引文件。所以对数据量不大，查询率不高更新率高的的列添加索引反而得不偿失。 面试官：当一条查询执行较慢时通常可以如何进行优化我：加索引！面试官：那么到底什么是索引，其底层又是如何实现的呢我：懵逼！ 索引的常见模型 索引的出现是为了提高查询效率，就像书的目录一样 常见的实...
摘要：哈希索引也不支持多列联合索引的最左匹配规则。树索引的关键字检索效率比较平均，不像树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。 B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。 B+树 B+树是为磁盘及其他存储辅助设备而设计一种平衡查找树（不是二叉树）。B+树中，所有...
摘要：而红黑树这种结构，明显要深的多。由于逻辑上很近的节点父子物理上可能很远，无法利用局部性，所以红黑树的渐进复杂度也为，效率明显比差很多。我的博客参考文献姜承尧著技术内幕存储引擎机械工业出版社，索引背后的数据结构及算法原理从及谈树 B-树 B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树 它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的...
摘要：一个表中可以有多个辅助索引。哈希算法是一种常用的算法，时间复杂度为。哈希算法存储引擎使用哈希算法来对字典进行查找，哈希碰撞采用转链表解决，哈希函数采用除法散列方式。所以说哈希索引只能用于搜索等值查询，范围查询是不能使用哈希索引。 在数据库中，如果索引太多，应用程序的性能可能会受到影响，如果索引太少，又会对查询性能产生影响。所以，我们要追求两者的一个平衡点，足够多的索引带来查询性能提高，...
阅读 1324·2023-04-26 01:54
阅读 1393·2021-10-11 10:58
阅读 1402·2021-09-30 09:55
阅读 2411·2021-09-22 16:05
阅读 1604·2021-07-25 21:37
阅读 2502·2019-08-29 18:45
阅读 1792·2019-08-29 16:44
阅读 1767·2019-08-29 12:34
