B+树
B+树是B树的一种变体，常用语数据库和操作系统的问题件系统中
- MySQL数据库的索引就是基于B+树实现的
下图为B+树的大概结构
B+树与前面研究的B树，B+树有以下特点：
-
分为内部节点（非叶子）与叶子节点两种节点
叶子节点为最下面一层的节点，除了叶子节点以外的节点，都佳作内部节点，叶子节点与内部节点有以下特性- 内部节点只存储key，不存储具体数据
- 叶子节点存储key和具体数据
所以，可以理解为，B+树是用来存储key-value的，所以内部节点只存储key，叶子节点才用来存储key和数据
-
所有叶子节点，会形成一条有序链表
从上图可以看出，叶子节点之间有箭头将节点串起来，并且节点的大小是有序的
当了解完B+树的特点以后，那么B+树到底有什么用呢？
由于B+树的非叶子节点，只用来存储key，所以当B+树节点与B树节点为同样大小的节点的话，B+树可以存储更多的key，因为一个key相对于一个节点具体数据来讲，占用的空间会更少，所以可以存储更多的key，这样，可以利用key快速找到对应的节点。
B树存储Key-Value的结构如下
所以，对比B树，B+树有以下一些优势
- 每个节点存储的key数量更多，树的高度更低
- 所有的具体数据都存储在叶子节点上，所以每次查询都要查到叶子节点，查询速度比较稳定
- 所有的叶子节点构成了一个链表，做区间查询时更方便
网友评论