数据库索引的存储结构:B+树

2019-02-14 本文已影响1人 one_zheng

数据库索引为什么要用树结构来做存储? (InnoDB引擎使用的是B+树)

1.树的查询效率高.
2.可以保持有序

二叉查找树跟B数的时间复杂度都是O(logn),为什么使用的是B树,而不是二叉查找树?

磁盘I/O消耗比较小.（一颗完全二叉树的高度大约是logN，而一个完全M叉树的高度大约是logᴍN）
数据库索引是存储在磁盘上的,索引的大小可能有几个G甚至更多.当我们利用索引查询的时候,不可能将整个索引全部加载到内存中,只能逐一加载每一个磁盘页,这里的磁盘页对应着索引树的节点.
如果我们利用二叉查找树作为索引结构,当树的高度是4,查找的值是10,流程如下:

二叉查找树的结构：

二叉查找树的结构.png

第1次磁盘I/O：

第1次磁盘I/O.png

第2次磁盘I/O：

第2次磁盘I/O.png

第3次磁盘I/O：

第3次磁盘I/O.png

第4次磁盘I/O：

第4次磁盘I/O.png

而B树是一种多路平衡查找数,它的每一个节点最多包含k个孩子,k被称为B树的阶.k的大小取决于磁盘页的大小.

一个m阶的B树具有如下几个特征:

1.根节点至少有两个子女.
2.每个中间节点包含k-1个元素和k个孩子,其中m/2<=k<=m.
3.每一个叶子节点都包含k-1个元素,其中m/2<=k<=m.
4.所有的叶子节点都位于同一层.
5.每个节点中的元素从小到大排序,节点当中k-1个元素正好是k个孩子包含的元素的值域划分.

一个3阶的B-树:

image.png

如果我们利用B-树作为索引结构,查询的数值是5,流程如下:

第1次磁盘I/O：

第1次磁盘I/O.png

在内存中定位（和9比较)：

在内存中定位（和9比较).png

第2次磁盘I/O：

第2次磁盘I/O：.png

在内存中定位（和2，6比较）：

在内存中定位（和2，6比较）.png

第3次磁盘I/O：

第3次磁盘I/O.png

在内存中定位（和3，5比较）：

在内存中定位（和3，5比较）.png

通过整个流程我们可以看出,B-树在查询中的比较次数其实不必二叉查找树少,尤其当单一节点的元素数量很多时,可是相比磁盘I/O的速度,内存中的比较耗时几乎可以忽略.所以只要树的高度足够低,I/O次数足够少,就可以提升查找性能.

B+树

一个m阶的B+树具有如下几个特征:

1.有k个子树的中间节点包含有k个元素(B树中k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点.
2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接.
3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素.

B+树结构例子:

B+树结构.png

B+树的好处主要体现在查询性能上.

在单元素查询的时候,B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点.比如我们要查找的是元素3

第一次磁盘I/O：

第一次磁盘I/O.png

第二次磁盘I/O：

第二次磁盘I/O.png

第三次磁盘I/O：

第三次磁盘I/O.png

B+树对比B-树的优势:

1.B+树的中间节点没有卫星数据(卫星数据,指的是索引元素所执行的数据记录,比如数据库中的某一行),所以同样大小的磁盘页可以容纳更多的节点元素
这意味着,数据量相同的情况下,B+树的结构比B-树更加"矮胖",因此查询时I/O次数也更少.
2.其次,B+树的查询必须最终查找到叶子节点,而B-树只要找到匹配元素即可,无论匹配元素处于中间节点还是叶子节点.
因此,B-树的查找性能并不文档(最好情况是只查根节点,最坏情况是查到叶子节点).而B+树的每一次查找都是稳定的(查询性能稳定)
1. B+树范围查询的效率比B-树高(范围查询简便)

B-树的范围查找过程

自顶向下，查找到范围的下限（3）：