发布时间:2022-08-19 12:28
前言
首先,我们知道的,我们用B树B+树就是为了增加我们索引的效率(增加查询效率)
我们都知道二叉查找树的查找的时间复杂度是O(log N),其查找效率已经足够高了,那为什么还有B树和B+树的出现呢?难道它两的时间复杂度比二叉查找树还小吗?
问题:
这就要抛出磁盘读写IO效率问题了,众所周知,IO查询效率很低,需要读磁盘将数据加载到内存当中,而在大量数据存储时,我们是不能一下子将所受数据加载到内存中,而是逐渐加载到磁盘页,每个磁盘页对应树的节点,也就是侧面体现出树的节点(数据)越多,磁盘页也就越多,IO也就越多(反推);——>树的深度和IO操作成振波
解决:
1.每个数据节点存储多个元素,也就是每次加载,数据变多,磁盘页上的数据变多
2.采用多叉树
B树
首先直接说他结构:一个指向当前数据的指针,一个往下面指的指针,还一个就是数据
一个m阶层的B树特征:当一个节点有k个孩子,比如头节点三个孩子,所以必有k-1个关键字,也就是两个关键字能够将子树的关键字划分为3个子集
查询:
以上图为例:若查询的数值为5:
第一次磁盘IO:在内存中定位(与17、35比较),比17小,左子树;
第二次磁盘IO:在内存中定位(与8、12比较),比8小,左子树;
第三次磁盘IO:在内存中定位(与3、5比较),找到5,终止。
整个过程中,我们可以看出:比较的次数并不比二叉查找树少,尤其适当某一节点中的数据很多时,但是磁盘IO的次数却是大大减少。比较是在内存中进行的,(因为我们比较是在内存中进行的,而我们一次能有多个数据,数据up了,所以大大减少了IO),相比于磁盘IO的速度,比较的耗时几乎可以忽略。所以当树的高度足够低的话,就可以极大的提高效率。相比之下,节点中的元素多点也没关系,仅仅是多了几次内存交互而已,只要不超过磁盘页的大小即可。
B+树
结构:指向下的指针+数据(叶子节点才有),下面用了一个联表,专门链接数据
1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据
都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小
自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
优点:一个节点存储的内容相比于B树,少了一个指针,所以说每次进行IO从硬盘加载数据到内存,能够加载的数据比B树要多一些,侧面体现出了B+树的优化所在
查找:
与B树不同的是,我们没有卫星查找(也就是索引元素指向的当前数据记录),意味着同样的磁盘页能够容纳更多的节点元素——>IO操作更少
需要补充的是,在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针;
B+树范围查找
首先先二分查找找到范围下限,此时我们链表的作用就体现出来了,可以通过叶子结点的链接顺序遍历直接找到上限,过程简单,效率高;
总结
B+树相比B树的优势:
1.单一节点存储更多的元素,使得查询的IO次数更少;
2.所有查询都要查找到叶子节点,查询性能稳定;
3.所有叶子节点形成有序链表,便于范围查询。