20190513面试B树

Dear 丶 2022-02-01 07:39 143阅读 0赞

## 1.什么是B树 ##

**B树**（英语：B-tree）是一种自平衡的[树][Link 1]，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在[对数时间][Link 2]内完成。B树，概括来说是一个一般化的[二叉查找树][Link 3]（binary search tree）一个节点可以拥有最少2个子节点。

## 2.B树适用的场景 ##

与[自平衡二叉查找树][Link 4]不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在[数据库][Link 5]和[文件系统][Link 6]的实现上。

## 3.B树特点 ##

*  保持键值有序，以顺序遍历
 *  使用层次化的索引来最小化磁盘读取
 *  使用不完全填充的块来加速插入和删除
 *  通过优雅的遍历算法来保持索引平衡

另外，B树通过保证内部节点至少半满来最小化空间浪费。一棵B树可以处理任意数目的插入和删除。

B树的弊端

*  除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。

（其他关联数组的实现，例如[三元搜索树][Link 7]或者开散列[哈希表][Link 8]，可以动态适应任意长度的键值）。

4.其他

1.  数据库系统维护着满足特定查找[算法][Link 9]的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。索引的实现通常使用B树及其变种B+树。

创建索引可以大大提高系统的性能。

第一、通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

第二、可以大大加快数据的检索速度，这也是创建索引的最主要的原因。

第三、可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。

第四、在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。

第五、通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。   
  
2.R树

R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。

如何查询特定的数据。又以餐厅为例，假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办？

1.  打开地图（也就是整个R树），先选择国内还是国外（也就是根结点）。
2.  然后选择华南地区（对应第一层结点），选择广州市（对应第二层结点），
3.  再选择天河区（对应第三层结点），
4.  最后选择天河城所在的那个区域（对应叶子结点，存放有最小矩形），遍历所有在此区域内的结点，看是否满足我们的要求即可。

### 相关知识： ###

一：为什么要用B树

磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过B树进行优化，提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢？我们可以根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

## 1.二叉搜索树： ##

*  1.所有非叶子结点至多拥有两个儿子（Left和Right）；
 *  2.所有结点存储一个关键字；
 *  3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70][]

2.**B-树**  
是一种多路搜索树（并不是二叉的）：

1.  若根结点不是终端结点，则至少有2棵子树
2.  除根节点以外的所有非叶结点至少有 M/2 棵子树，至多有 M 个子树（关键字数为子树减一）
3.  所有的叶子结点都位于同一层

如：（M=3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1][]

因为 B 树的子树大小排序规则，因此在 B 树中查找数据时，一般需要这样：

1.  从根节点开始，如果查找的数据比根节点小，就去左子树找，否则去右子树
2.  和子树的多个关键字进行比较，找到它所处的范围，然后去范围对应的子树中继续查找
3.  以此循环，直到找到或者到叶子节点还没找到为止

用一张图对比平衡二叉树和 B 树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2][]

可以看到，**B 树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度。**

我们知道，平衡的树之所以能够加快查找速度，是因为在添加、删除的时候做了某些操作以保证平衡。

平衡二叉树的平衡条件是：**左右子树的高度差不大于 1**；而 B 树的平衡条件则有三点：

1.  叶子节点都在同一层
2.  每个节点的关键字数为子树个数减一（子树个数 k 介于树的阶 M 和它的二分之一
3.  子树的关键字保证左小右大的顺序

也就是说，一棵 3 阶的 B 树（即节点最多有三个子树），每个节点的关键字数最少为 1，最多为 2，如果要添加数据的子树的关键字数已经是最多，就需要**拆分节点，调整树的结构。**

## B树适用场景 ##

文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：

*  Windows：HPFS 文件系统
 *  Mac：HFS，HFS+ 文件系统
 *  Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
 *  数据库：ORACLE，MYSQL，SQLSERVER 等中
 *  数据库：ORACLE，MYSQL，SQLSERVER 等中

3.**B+树**

由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引，而B树则常用于文件索引。

# B树和B+树的区别 #

一棵 B+ 树需要满足以下条件：

1.  节点的子树数和关键字数相同（B 树是关键字数比子树数少一）
2.  节点的关键字表示的是子树中的最大数，在子树中同样含有这个数据
3.  叶子节点包含了全部数据，同时符合左小右大的顺序

如：（M=3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 3][]

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；  
B+的特性：  
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；  
2.不可能在非叶子结点命中；  
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；  
4.更适合文件索引系统；

B+ 树的三个优点：

1.  层级更低，IO 次数更少
2.  每次都需要查询到叶子节点，查询性能稳定
3.  叶子节点形成有序链表，范围查询方便

简单概括下 B+ 树的三个特点：

1.  关键字数和子树相同
2.  非叶子节点仅用作索引，它的关键字和子节点有重复元素
3.  叶子节点用指针连在一起

首先第一点不用特别介绍了，在 B 树中，节点的关键字用于在查询时确定查询区间，因此关键字数比子树数少一；而在 B+ 树中，节点的关键字代表子树的最大值，因此关键字数等于子树数。

第二点，除叶子节点外的所有节点的关键字，都在它的下一级子树中同样存在，最后所有数据都存储在叶子节点中。根节点的最大关键字其实就表示整个 B+ 树的最大元素。

第三点，叶子节点包含了全部的数据，并且按顺序排列，B+ 树使用一个链表将它们排列起来，这样在查询时效率更快。

由于 B+ 树的中间节点不含有实际数据，只有子树的最大数据和子树指针，因此磁盘页中可以容纳更多节点元素，也就是说同样数据情况下，B+ 树会 B 树更加“矮胖”，因此查询效率更快。

B+ 树的查找必会查到叶子节点，更加稳定。

有时候需要查询某个范围内的数据，由于 B+ 树的叶子节点是一个有序链表，只需在叶子节点上遍历即可，不用像 B 树那样挨个中序遍历比较大小。

4.**B\*树**

B\*树是B+树的变种，相对于B+树他们的不同之处如下：

（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b\*树的初始化个数为（cei(2/3\*m)）

（2）B+树节点满时就会分裂，而B\*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 4][]

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B\*树额分解次数变得更少；

## **5、 总结** ##

**1、相同思想和策略**

从平衡二叉树、B树、B+树、B\*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；

**2、不同的方式的磁盘空间利用**

不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；

**小结**

1.  B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
2.  B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
3.  B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
4.  B\*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

参考

[https://zhuanlan.zhihu.com/p/27700617][https_zhuanlan.zhihu.com_p_27700617]

[https://www.jianshu.com/p/332caf8bed3a?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][https_www.jianshu.com_p_332caf8bed3a_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

[https://juejin.im/entry/5b0cb64e518825157476b4a9][https_juejin.im_entry_5b0cb64e518825157476b4a9]

https://blog.csdn.net/yutianxin123/article/details/52269810

[https://blog.csdn.net/hust\_dxxxd/article/details/50905446][https_blog.csdn.net_hust_dxxxd_article_details_50905446]

[Link 1]: https://zh.wikipedia.org/wiki/%E6%A0%91_%28%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%29
[Link 2]: https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6#%E5%AF%B9%E6%95%B0%E6%97%B6%E9%97%B4
[Link 3]: https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9
[Link 4]: https://zh.wikipedia.org/wiki/%E8%87%AA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91
[Link 5]: https://zh.wikipedia.org/wiki/%E6%95%B0%E6%8D%AE%E5%BA%93
[Link 6]: https://zh.wikipedia.org/wiki/%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F
[Link 7]: https://zh.wikipedia.org/wiki/%E4%B8%89%E5%85%83%E6%90%9C%E7%B4%A2%E6%A0%91
[Link 8]: https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
[Link 9]: http://lib.csdn.net/base/31
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70]: /images/20220201/d89ef81bd689440bb17d57da0c61971b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1]: /images/20220201/2f95f7716b5b4b0498b1b6a757a9ae36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2]: /images/20220201/98536459060c4fd6bdf5a05357a7a3bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 3]: /images/20220201/f325c5a43e9a4a6c977bd4157e803bc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 4]: /images/20220201/cdd7e2265db04d309cbce64f0c33b4bb.png
[https_zhuanlan.zhihu.com_p_27700617]: https://zhuanlan.zhihu.com/p/27700617
[https_www.jianshu.com_p_332caf8bed3a_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]: https://www.jianshu.com/p/332caf8bed3a?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation
[https_juejin.im_entry_5b0cb64e518825157476b4a9]: https://juejin.im/entry/5b0cb64e518825157476b4a9
[https_blog.csdn.net_hust_dxxxd_article_details_50905446]: https://blog.csdn.net/hust_dxxxd/article/details/50905446