数据库索引为什么要用树结构来做存储? (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+树的每一次查找都是稳定的(查询性能稳定) - B+树范围查询的效率比B-树高(范围查询简便)
B-树的范围查找过程
自顶向下，查找到范围的下限（3）：
自顶向下，查找到范围的下限（3）.png
中序遍历到元素6：
中序遍历到元素6.png
中序遍历到元素9:
中序遍历到元素9.png
中序遍历到元素11，遍历结束：
中序遍历到元素11，遍历结束.png
B+树的范围查找过程
自顶向下，查找到范围的下限（3）：
image.png
通过链表指针，遍历到元素6, 8
通过链表指针，遍历到元素6, 8.png
通过链表指针，遍历到元素9, 11，遍历结束：
image.png
网友评论