【LSP】B-树、B+树初探

无名

一、背景
数据库索引使用树结构存储(注：MySQL使用B+树)。
Q：索引为什么不使用二叉查找数结构？
A：考虑到磁盘IO；
数据库索引是存储在磁盘上的，当数量比较大时索引大小可能几个G。不可能把整个索引全加载到内存中，能做的只有逐一加载每一个磁盘页(对应着索引树的节点)；
为了减少磁盘IO的次数，把“瘦高”的树结构变得“矮胖”。这就是B-树的特征之一；
二、B-树
1.介绍
B-树是一种多路平衡查找树，以m阶(B树中一个节点的子节点数目的最大值)为例，它的每一个节点最多包含k(m/2 <= k <= m)个孩子,
其中k的大小取决于磁盘页的大小。有自平衡的能力。
2.特征
<1>根节点至少有两个子女；
<2>每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m；
<3>每个叶子节点都包含k-1个元素，其中 m/2 <= k <= m;
<4>所有叶子节点都位于同一层上；
<5>每个节点中的元素都是从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

三、B+树
1.介绍
B+树是基于B-树的一种变体，有着比B-树更高的查询性能。
2.特征
<1>有K个子树的中间节点包含K个元素(B-树中是k-1个元素)，每个元素不保存数据只用来索引，所有数据都保存在叶子节点上;
<2>所有叶子节点中包含了全部元素的信息，及指向这些元素记录的指针，且叶子节点本身以关键字的大小自小到大顺序链接；
<3>所有的中间节点元素同时存在于子节点，在子节点元素中是最大or最小的元素；

注：
<1>"——>"：指针
<2>最大元素在根节点
<3>卫星数据(Data)：指的是索引元素所指向的数据记录,比如数据库中的某一行在B-树中无论中间节点还是叶子节点都带有卫星数据，而在
B+树中只有叶子节点有，中间节点仅仅是索引没有任何数据关联。
<4>与B-树的不同：
1>B+树中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素；
2>B+树的查询必须找到叶子节点，而B-树只要找到匹配元素，因此B+树更稳定；
3>范围查找时，B-树要反复遍历，而B+树只在链表上做遍历即可。
PS:关于数据库索引
一个表中有多个索引就有多个B+树，只有主键索引存储整张表数据；
索引数据结构：二叉树、红黑树、Hash表、B-树；
索引分为：单值索引、联合索引(多列标识唯一的一行数据，把多个字段联合起来作为索引)

PS2：简单概述B-树、B+树
B-树：叶子节点具有相同的深度，叶子节点的指针为空，所有索引元素不重复，节点中元素索引从左到右递增排列；
B+树：非叶子节点不存储data(卫星数据),只存储索引(冗余)可以放更多索引，叶子节点包含所有索引字段，叶子节点用指针连接提高区间访问的性能。