B+树
# 1. 红黑树与B树的区别
- B树又叫平衡多路查找树。B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。与红黑树很相似，但在降低磁盘I/0操作方面要更好一些。
- 红黑树与B树的区别在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的 B树的高度也为O（lgn） ，但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所以， B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作
# 2. B树
B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：
每个结点最多有M-1个key，并且以升序排列；
每个结点最多能有M个子结点；
根结点至少有两个子结点；
# B树的优点
由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value。
# 3. B+树
B+树是对B树的一种变形树，它与B树的差异在于：
- 非叶结点仅具有–索引作用，也就是说，非叶子结点只存储key，不存储value；
- 树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据。
# 3.1 B+树存储数据
若参数M选择为5，那么每个结点最多包含4个键值对，我们以5阶B+树为例，看看B+树的数据存储。
# 3.2 B+ 树的优点
由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的
keyB+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历
# 4. B+树在数据库中的应用
在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这个索引就是B+树这种数据结构实现的。
# 4.1 未建立主键索引查询
执行select * from user where id=18,需要从第一条数据开始，一直查询到第6条，发现id=18，此时才能查询出目标结果，共需要比较6次；
# 4.2 建立主键索引查询
执行select * from user where id = 18 ，如果有了索引，由于B+树的叶子结点形成了一个有序链表，所以我们只需要找到id为12的叶子结点：
18 > 12，在12节点的右孩子- 遍历右孩子链表，根据
key=18，找到其地址即可
按照遍历链表的方式顺序往后查即可，共查询了3次，效率非常高。
在区间查询时，效率体现的更加明显