B+树

1.多叉树(multiway tree)

树家族是为了实现方便快捷的搜索而存在的,其搜索的时间复杂度与树的深度相关。在一定的数据条件下,树的深度和宽度是相互制约的,增加树的宽度可以降低树的深度,从而提高树的搜索效率,多叉树由此诞生。

2.多叉搜索树(multiway search tree)

为了使多叉树的处理更容易,将对每个节点内的元素按某个方式进行排序,从而产生多叉搜索树。根据定义,m叉搜索树有如下特征:

每个节点最多有m个子节点(0~m)

每个节点最多有m-1个元素(1~m-1)

每个节点中的元素按升序排列

前i个子节点的元素都小于第i个元素

后i+1个子节点的元素都大于第i个元素

下图为一个4叉搜索树。

在该4叉搜索树中查找键值8的过程如下。

3.B树(B-tree)

m阶B树是一颗m叉搜索树,相比一般m叉搜索树,m阶B树有如下特征:

根节点至少有2个孩子

除根节点以外,所有内部节点至少有m/2(进一法)个子节点(m/2~m)

所有外部节点在同一层

下图为5阶B树,根节点有3个孩子(大于2);除根节点以外,所有内部节点的子节点分别为5个,3个,3个(等于5/2);所有外部节点在同一层。

4.B+树(B+ tree)

B+树是对B树的一种变形树,它与B树的差异在于:

有k个子节点的节点必然有k个元素

非叶子节点仅具有索引作用,跟记录有关的信息均存放在叶子节点中

树的所有叶子节点构成一个有序链表,可以按照元素排序的次序遍历全部记录

B树和B+树的区别在于,B+树的非叶子节点只包含导航信息,不包含实际的值,所有的叶子节点和相连的节点使用链表相连,便于区间查找和遍历。

B+树的优点

由于B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。

B+树的叶子节点都是相连的,因此只要遍历叶子节点就可以实现整颗树的遍历。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历,相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

B+树的缺点

但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

因为B+树比B树的读写代价更低,所以B+树比B树更适合操作系统的文件索引和数据库索引。

5.B+树应用

目前常见的三种存储引擎是:哈希、B+树、LSM树

哈希存储引擎:是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value存储系统。对于key-value的插入以及查询,哈希表的时间复杂度都是O(1),如果不需要有序的遍历数据,哈希表性能最好。

B+树存储引擎是B+树的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描(B+树的叶子节点之间的指针),对应的存储系统就是关系数据库(Mysql等)。

LSM树(Log-Structured MergeTree)存储引擎和B+树存储引擎一样,同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊,LSM树和B+树相比,LSM树牺牲了部分读性能,用来大幅提高写性能。

上面三种引擎中,B+树存储引擎的代表有MySQL MyISAM存储引擎。MyISAM引擎使用B+Tree作为索引结构,叶子节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

这里假设表一共有三列,我们以Col1为主键,则上图是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+树算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

7.性能

参考:

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/multiway.html

https://blog.csdn.net/u010853261/article/details/78217823

http://www.cnblogs.com/xyxxs/p/4440187.html

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181207G1KM5J00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券