一棵B+树
b+树的节点
节点类型
B+树的节点有2种类型：
- 1.叶结点：叶节点在B+树的最底层（所有叶节点都在同一层），叶结点中存放索引值、指向记录的指针、指向下一个叶结点的指针。叶结点内的索引值是记录中键的拷贝，这些索引值以排好序的形式，从左到右分布在叶节点中，形成一个有序链表。叶子节点包含了全部节点的信息
叶节点
- 2.内部结点：所有非叶结点都属于内部结点，每一个父节点的元素都出现在子节点中，是子节点的最大或最小元素
注意：根节点的最大元素等是整个B+树的最大元素
和B树的区别
在B+树中，只有叶子节点带有卫星数据（卫星数据：索引元素所指向的数据记录，比如数据库中的某一行）
B+树中的卫星数据
在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
与B+数不同的是，B树中的所有节点都带有卫星数据
B树中的卫星数据
B+树比B树具有更好的查询性能
对于单行查询
比如我们要查找3
在B+树上的单行查询
和B树的查询流程差不多，但有2点不同
- B+树的中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的非叶节点，在数据量相同的情况下，B+树的结构比B树更“矮胖”，因此查询时IO次数更少.
- B+树的查询最终查找到叶子节点，而B树的查询可能匹配到叶子节点也可能匹配到中间节点，所以B树的查找性能并不稳定
对于范围查询
比如查找[3,11]
B树的查找过程
自顶向下，查找到范围的下限（3）：
中序遍历到元素6：
中序遍历到元素8：
中序遍历到元素9：
中序遍历到元素11，遍历结束：
B+树的查找过程
自顶向下，查找到范围的下限（3）：
通过链表指针，遍历到元素6, 8：
通过链表指针，遍历到元素9, 11，遍历结束：
显然B+树的范围查询比B树更便捷
总结：
B+树的特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+树的优势：
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。
