简单理解B树和B+树

前言

首先，我们知道的，我们用B树B+树就是为了增加我们索引的效率（增加查询效率）

我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？

问题：

这就要抛出磁盘读写IO效率问题了，众所周知，IO查询效率很低，需要读磁盘将数据加载到内存当中，而在大量数据存储时，我们是不能一下子将所受数据加载到内存中，而是逐渐加载到磁盘页，每个磁盘页对应树的节点，也就是侧面体现出树的节点（数据）越多，磁盘页也就越多，IO也就越多（反推）；——>树的深度和IO操作成振波

解决：

1.每个数据节点存储多个元素，也就是每次加载，数据变多，磁盘页上的数据变多

2.采用多叉树

B树

首先直接说他结构：一个指向当前数据的指针，一个往下面指的指针，还一个就是数据

一个m阶层的B树特征：当一个节点有k个孩子，比如头节点三个孩子，所以必有k-1个关键字，也就是两个关键字能够将子树的关键字划分为3个子集

 查询：

 　以上图为例：若查询的数值为５：
　　第一次磁盘ＩＯ：在内存中定位（与17、35比较），比17小，左子树；
　　第二次磁盘ＩＯ：在内存中定位（与８、12比较），比８小，左子树；
　　第三次磁盘ＩＯ：在内存中定位（与3、5比较），找到5，终止。
整个过程中，我们可以看出：比较的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少。比较是在内存中进行的，（因为我们比较是在内存中进行的，而我们一次能有多个数据，数据up了，所以大大减少了IO），相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。
 

B+树

结构：指向下的指针+数据（叶子节点才有），下面用了一个联表，专门链接数据

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据
都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小
自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

优点：一个节点存储的内容相比于B树，少了一个指针，所以说每次进行IO从硬盘加载数据到内存，能够加载的数据比B树要多一些，侧面体现出了B+树的优化所在

 查找：

 与B树不同的是，我们没有卫星查找（也就是索引元素指向的当前数据记录），意味着同样的磁盘页能够容纳更多的节点元素——>IO操作更少

 需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针；

B+树范围查找

首先先二分查找找到范围下限，此时我们链表的作用就体现出来了，可以通过叶子结点的链接顺序遍历直接找到上限，过程简单，效率高；

 总结

B+树相比B树的优势：
　　1.单一节点存储更多的元素，使得查询的IO次数更少；
　　2.所有查询都要查找到叶子节点，查询性能稳定；
　　3.所有叶子节点形成有序链表，便于范围查询。