B+树的Java实现(B+ Tree) - 桐小目的秘密基地 - CSDN博客·
定义
M阶树每个节点最多有M个子节点；
叶子节点均在同一列由一个链表构成
可以看作一个完美多叉树
B+树
与B树的优势:
父类节点的数组中只需要存储key不需要多存储data节省了空间。
扩容:
大于M节点则，左边保留M/2节点，右面为M-1节点，然后父节点为拆开的两个段上右边的节点。
数据结构
父节点（索引节点）
父亲节点指针
子节点数组指针
子节点数量
子节点Key数组
叶子节点（数据节点）
一个Node数组还有左右两个指针
单个Node(一个数据)
类似一个map(K,V)
注意：
插入1万个节点耗时0.047s
插入10万个节点耗时0.125s
插入1百万个节点耗时3s
插入1千万个节点耗时36s
但是：查询都是0.9微秒！94853纳秒！ 查询的性能太可怕了。
这要不看一下代码真的是太可惜了详情见上面的链接
拓展：
InnoDB 一页16K 一个叶子节点1K 16条数据
上文我们已经说明单个叶子节点（页）中的记录数 =16K/1K=16
我们假设主键 ID 为 bigint 类型，长度为 8 字节，而指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节，我们一个页中能存放多少这样的单元，其实就代表有多少指针，即 16384/14=1170。
那么可以算出一棵高度为 2 的 B+ 树，能存放 1170*16=18720 条这样的数据记录。
根据同样的原理我们可以算出一个高度为 3 的 B+ 树可以存放： 1170*1170*16=21902400 条这样的记录。
（InnoDB 默认的高度是3因为高度越高索引的重复率越高且IO开销越大）
