为什么使用B+树

B+树的优势：

1.单一节点存储更多的元素，使得查询的IO次数更少。

2.所有查询都要查找到叶子节点，查询性能稳定。

3.所有叶子节点形成有序链表，便于范围查询。

B树

缺点：

1. 索引存值，然而数据库内容和索引分开存储的

2. 索引存值，每次查找都要访问数据库，效率低

3. 不适合范围查找

在B树的每一个节点中，都不止存储一个值，具体存储的值的个数依赖于B树的阶。而我们在查找一个值的过程中，需要对当前所在的节点包含的所有值进行一个遍历，以此来确定当前查找的值是否在当前节点中。这也就意味着，相比于二叉搜索树，平衡二叉树，红黑树等数据结构，B树查找一个值需要比较更多的次数。假设一棵B树的阶是100，那也就意味着在最坏情况下，我们在每一个访问到的节点中，都需要比较100次，而前面提到的三种数据结构比较的次数不会超过树的深度，也就是只需要少量的比较次数。既然B树相比较于它们需要比较更多的次数才能找到相应的值，那为什么还要B树呢？这取决于实际的应用场景。

说到B树，大部分首先想到的就是数据库的索引，MySQL中使用的索引主要为BTree索引（实际是B+树实现的，这个后面再谈）。从上面的B树结构我们可以看到，B树中使用大量的指针维护节点之间的关系，这也就意味着B树在物理存储上并不是连续的。单个节点中的数据是连续存储，但是多个节点之间一般都是单独存储，然后通过指针相互引用。在实际的存储中，BTree索引一般被存放在磁盘中，然后只有需要使用时，才将使用到的部分节点加载进内存，进行比较判断。

为什么不一次性将BTree索引全部加载进内存？因为在实际生产中，索引往往需要维护百万甚至千万行数据，这就导致索引本身占据大量的内存，再加上我们使用的常常不止一个索引，再加上内存中需要运行其他程序，所以将索引一次性加载进内存是不现实的事情。只有当前需要使用的部分才被加载进内存，而不使用的部分则留在磁盘或者从内存中移除。

而上面这种使用到才进行加载的方式有一个什么问题？我们每次需要查找树中的一个节点，都需要进行一次磁盘IO，将这个节点从磁盘中加载进内存。而对于B树或者说之前提到的平衡二叉树等数据结构，最多需要访问的节点的个数，实际上就是树的深度（想想搜索一个值的过程就能明白）。对于B树来说，他每一个节点可以存储多个值，而平衡二叉树等二叉结构，每一个节点只存储一个值，这也就意味着在值的个数相等的情况下，B树的深度小于二叉树的深度。这也就意味着以B树作为索引，可以进行更少次数的磁盘IO。

对于一棵含有n个元素的树，二叉搜索树的深度在n-log2(n)之间，而平衡二叉树的深度是log2(n)，红黑树与平衡二叉树类似，平均深度也是log2(n)。然而，B树设计了一种高效简单的维护操作，使B树的深度维持在约log(ceil(m/2))(n)~logm(n)之间，大大降低树高（ceil是向上取整函数，例如5/2 = 3）。

这里面临一个什么问题？磁盘的速度，相对于内存来说非常的缓慢，磁盘查找的速度比内存查找慢100000倍左右。也就是说，从磁盘中找到1个数据所花费的时间，可以从内存中查找100000个数据。这也就意味着我们在使用索引查找数据的过程中，时间主要是花费在了磁盘IO上，而不是数据的比较上。所以，我们希望尽可能少地进行磁盘IO。而B树作为索引，由于树的深度较小，相比于那些二叉树，可以进行更少的磁盘IO，这就是B树最大的优势。

二叉树中，一个节点一般只存储一个元素，而在将磁盘的数据加载进内存中时，实际上是按页进行加载的，页是每次从磁盘加载进内存的数据的最小单位，一般为4K。这也就意味着我们使用这些二叉树的数据结构时，加载一个节点所在的页进入内存时，这个页中有大量内存都是浪费的。而B树中每一个节点可以存储多个数据，于是我们可以通过修改B树的阶，让他的每一个节点大致占用一个页（4K）的大小，以此最大限度的减少B树的深度，提高内存利用率。

B+数

B+树相对于B树主要做了如下的修改：

B+树中的每一个非叶子节点并不存储值value，只存储键key，而具体的value全部存放在叶子节点中，这也就意味着每次查找需要访问的节点数量都是固定的，都需要向下查找到叶子节点；
每一个叶子节点都有一个指向下一个叶子节点的指针，所有的叶子节点相互串联，组成一个线性的结构；
对于一个m阶的B+树，每一个节点最多只有m个子节点，同时存储m个key（对于m阶的B树，只有m-1个key）；
每一个子节点中最小（或最大）的key，也包含在父节点中（这个通过下面的例子理解）；

在最下层的叶子节点中，存储了全部的key值（尽管有些key已经在上层节点出现过），同时不仅存储了key值，还存储了这些key值对应的value。除此之外，每一个叶子节点都包含一个指针，指向下一个叶子节点。这些叶子节点相互串联，组成了一个key值从小到大排好序的线性结构。

我们在树中存储了value，但是由于value存储在叶子节点中，所以对于作为索引的非叶子节点来说，并没有增加它们的大小，从而并没有导致树的高度增加。除此之外，由于value都存储在叶子节点中，并且叶子节点相互串联，所以非常方便进行范围查询。比如说上图，我们要查找key为26-60对应的数据，那我们首先查找26所在的叶子节点，发现它在第三个叶子节点，于是我们将第三个叶子节点读入内存，然后发现并不包含全部数据，于是通过指针找到第四个叶子节点，将第四个叶子节点读入内存，还不包含全部，于是将第五个叶子节点也读入，这时就包含全部数据了。