(59)王道数据结构-B+树

原文地址:B+树

基本概念

它不像B树那样，B树并不是只有最后一行会存储卫星数据，此时比较凌乱。因为只有最后一行存储卫星数据，使用B+树，同样大小的磁盘页可以容纳更多的节点元素，这就意味着，数据量相同的情况下B+树比B树高度更低，减小磁盘IO的次数。

其次，B+树的查询必须最终查找到叶子节点，而B树做的是值匹配，到达结点之后并不一定能够匹配成功，所以B树的查找性能并不稳定，最好的情况是只查根节点即可，而最坏的情况则需要查到叶子节点，但是B+树每一次查找都是稳定的，因为一定在叶子结点。

并且得益于最后一行的链表结构，B+树在做范围查询时性能突出。很多数据库都在采用B+树作为底层数据结构，比如MySQL就默认选择B+Tree作为索引的存储数据结构。

1.其中最后一层形成了一个有序链表，在我们需要顺序查找时，提供了极大的帮助

2.除了最后一层之外，其他结点中存放的值仅仅充当了一个指路人的角色,告诉你你需要的数据在哪一边

3.比如根节点有10和18，因为这里是取得最大值，那么整棵树最大的元素就是18了

4.我们现在需要寻找一个小于18大于10的数，就可以走右边去查找

基本性质

1.有k个子树的中间结点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据（卫星数据，就是具体需要保存的内容）都保存在叶子结点

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点按照从小到大的顺序连接

3.所有的根结点元素都同时存在于子结点中，在子节点元素中是最大（或最小）元素。

存储结构