B+树的内部节点包括：Key键值，Index索引值
B+树的叶子节点包括：Key键值，Index索引值，Data数据
B+树的内部节点也可称为索引节点，叶子节点也可称为外部节点
B+树是对B树的一种变形树，数据节点都存储在叶节点上，叶子节点之间通过指针按照顺序链接。
它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
如下图，是一个B+树:
B+树结构参考
下图是B+树的插入动画：
B+树构建参考
B树、B+树和二叉树、平衡二叉树一样，都是经典的数据结构。
B+树由B树和索引顺序访问方法（ISAM，是不是很熟悉？对，这也是MyISAM引擎最初参考的数据结构）演化而来，但是在实际使用过程中几乎已经没有使用B树的情况了。
B+树的定义十分复杂，因此只简要地介绍B+树：B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接。
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+ 树的优点在于：
由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：
image.png
分析
对于一颗节点为N度为M的子树，查找和插入需要logM-1N ~ logM/2N次比较。这个很好证明，对于度为M的B树，每一个节点的子节点个数为M/2 到 M-1之间，所以树的高度在logM-1N至logM/2N之间。
这种效率是很高的，对于N=62*1000000000个节点，如果度为1024，则logM/2N <=4，即在620亿个元素中，如果这棵树的度为1024，则只需要小于4次即可定位到该节点，然后再采用二分查找即可找到要找的值。
网友评论