24丨索引的原理：我们为什么用B+树来做索引？

一、数据库索引，为什么不适用用二叉树： 1. 平衡二叉树必须满足（所有节点的左右子树高度差不超过1）。执行插入还是删除操作，只要不满足上述条件，就要通过旋转来保持平衡，而旋转是非常耗时的，所以AVL树适合用于查找多的情况。 2. 二叉树的数据结构，会导致“深度”，比较深，这种“瘦高”的特性，加大了平均查询的磁盘IO次数，随着数据量的增多，查询效率也会受到影响； 二、B+ 树和 B 树在构造和查询性能上有什么差异呢？ B+ 树的中间节点并不直接存储数据。 1. B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 2. B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。 3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

B树和B+树的区别： 1、B树非叶子结点存储数据；B+树非叶子结点不存储数据只存索引。 2、B树叶子结点没有使用双向链表串连；B+树叶子结点使用双向链表进行串连，为了支持区间查询。

1.为什么数据库索引采用 B+ 树，而不是平衡二叉搜索树？ 数据库索引存储在磁盘上，平衡二叉树虽然查找效率高，但“高瘦”，进行的IO次数比平衡二叉搜索树多。 2.B+ 树和 B 树在构造和查询性能上差异？ （1）B树的每个节点含有卫星数据，而B+树中间节点含有指向卫星数据的指针，叶子节点才存有卫星数据。这样一来每次进行B+树查询都需要查询到叶子节点，性能更稳定，而且B+树节点只存储指向卫星数据的指针，这样一个磁盘页能存储更多节点。 （2）B+树范围查询更有优势，因为叶子节点直接串联成一条链表 （3）B+树单一结点比起B树存储更多元素，IO更少

请问，文中的B树图，元素“68”是在“65”到“85”之间，为什么属于第一棵子树呢？

【对于一个 100 阶的 B 树来说，如果有 3 层的话最多可以存储约 100 万的索引数据】是怎么计算出 100 万的，按照前面的描述指数是关键字的个数+1 没弄明白，求解答？

B+ 树中间节点只保存索引，不保存数据，所以一个节点能放更多的索引，同样的索引树，相比于 B 树，B + 树的深度会更少。

记得刚接触编程的时候，很不习惯计数要从0开始，后来用围栏法勉强不会搞错计数顺序了，还是一直不解为什么要这样设计。 今天看老师讲解b树和b＋树，有个类似发现，b树就好像很多人习惯了的从1开始计数，或者举例说要把一段绳子截成三段，你只需截2次即可； b ＋树就好比用围栏隔出若干空间，比如隔出两块空间需要三个围栏板，脑海里联想下公测的蹲坑隔间就能理解了。 按我的理解b＋树之所以显示优于b树，可能跟前后两端的数据空间有关，这跟将数据序列设计成从0开始计数而非从1开始是出于同样的考量。

老师讲得好，深入浅出。

首先感谢前面认真学习数据结构的自己，这下不就用到了！所以学习这一节的时候就感觉非常爽！ 1、数据库索引为什么采用B+树而不采用平衡二叉搜索树？ 数据库的索引是存储在磁盘上的，每次查询都需要涉及I/O操作，I/O操作的次数越多，那么查询所化的时间就越长，性能也就越低，所以引入了平衡二叉搜索树来存储数据，本来平衡二叉搜索树的查询效率是非常高的，但是当数据量很大的时候，平衡二叉搜索树的高度就会很高，每次进行查询的时候也就需要经历很多的节点，自然也就增加了I/O操作的次数，严重的降低了性能，要是你查询的数据刚好在根节点那还好，都是一样的，但是这种情况的概率只有1%，属于极端情况(自己脑补)......所以在此引入了B+树这个数据结构（B树老师已经说得很清楚了，我就不说了），降低了树的高度，减少了I/O操作的次数，提高了查询的效率！ 2、B和B+树在构造上有什么差异吗？ B+树的查询效率更稳定的，因为每次都必须查询到叶子节点才能找到最终的数据，而B树查询的数据也许在叶节点上，也许在叶子节点上，这样就会造成查询的效率不稳定！ B+树的查询效率更高，因为B+树更矮更胖（肉多，哈哈），所以B+树的高度越小，查询时产生的I/O次数也就更少，性能自然就高！

网上还看到B-tree是和B tree一个意思吗？