【数据结构】B树

良辰美景❤️

风花雪月❤️

似水年华❤️

岁月静好❤️

又拒绝了三个女生

我真是一个优秀的男孩

看着他们远去的身影，有点落寞

我只能默默的说声抱歉 

你们这个楼盘、保险、理财产品我是真的买不起

今天讨论的话题是

B-tree

🌈🌈🌈

先养眼，再看题

❤️

今天还是小姐姐

前言

> 面试中可能出现的场景

> 面试官：Mysql数据库用过么？里面的索引是基于什么数据结构。

> 我：？？？

> 面试官：请简单说下B+树的实现细节？B和B+有什么区别？

> 我：？？？

> 面试官：回去等通知吧。

> 我：？？？ 

那么在此

我会大致简单的说下B树

[toc]

- B树

    - 概念

    - 特性

    - 看图加深理解概念

    - 数据库索引

        - B树如何查找

        - 二叉树如何查找

        - 两者主要差别

- 总结

概念

> 一棵m阶B树是一棵平衡的m路搜索树。它或者是空树，它是一种平衡的多叉树，称为B树或B-树

（小声逼逼：关于B树和B-树，其实是翻译问题，本来是B-tree，有的翻译是B树有的翻译是B-树，整的都懵逼了）

特性

> 下面的概念又懵逼了，但是先看下，等后面内容看懂了再看前面的也不迟。

1. 根节点至少有两个孩子。

2. 每个中间节点都包含 k - 1 个元素和 k 个孩子，其中 m/2 <= k <= m。

3. 每一个叶子节点都包含 k - 1 个元素，其中 m/2 <= k <= m。

4. 所有的叶子节点都位于同一侧。

5. 每个节点中的元素从小到大排列，节点当中的 k - 1 个元素正好是 k 个孩子包含的元素的值域划分。

图是一棵m=3的3阶B树，可以看出，有的节点是多个元素，并且和二叉树长得也差不多呢（左节点的所有元素比父亲元素都小）。

比如对于（3，7）这个节点。两个元素把这个节点分割成三个值域，即可以有3个孩子。

- 2相当于3节点的左孩子节点

- 4,6相当于3节点的右孩子节点，同时也是7的左孩子节点

- 9是7的右孩子节点

首先B树和二叉树多相似，都是有序的，且左孩子小右孩子大，只是B树会一个节点上有多个元素。

那么问题来了，数据库的索引为什么要用B+树，二叉树查找的效率不是要快么。

首先咱们先看图，细细品这两个查找的效率比较

B树是如何查找的

需求：我们需要查询元素9

第一次比较
和10比较，比10小，所以在10的左孩子找。

第二，三次比较
和3比较，比3大，

和7比较，比7大，

所以在7的右孩子找。

第四次比较
和9比较，相等，找到目标树，返回。

所以最终的结果需要4次比较

简单粗暴和B树一样

第一次比较

和10比较，比10小，所以在10的左孩子找

第二次比较

和6比较，比6大，所以在6的右孩子找

第三次比较

和7比较，比7大，所以在7的右孩子找

第四次比较

和9比较，相等，找到目标树，返回

so，B树和二叉树都是经历4次比较，而且，B树的每一个节点，如果存放的元素比较多，那么B树的比较次数会更多，为什么要B树的下来要比二叉树要快呢？

答案：其实从算法逻辑上来讲，二叉查找树的查找效率和比较次数都是最小的。但是，我们需要考虑一个很现实的问题：磁盘IO即磁盘的寻址加载次数

首先，数据库索引是存储在磁盘上的，当数据量比较大的时候，索引的大小可能就有几个G甚至更多

然后，当我们利用索引查询的时候，能把整个索引全部加载到内存么？显然不可以。

Tips：在把磁盘中的数据加载到内存中的时候，是以页为担心来加载的，并且，节点与节点之间的数据是不连续的

so，我们能做的只有逐一加载每一个磁盘页，这个磁盘页就是索引树的节点。

对于二叉查找树，我们可能需要进行4次寻址加载

对于B树，由于B树的每一个节点，可以存放多个元素，所以磁盘寻址加载的次数会比较少，可能只进行3次寻址加载

我们知道，在内存的运算速度是非常快的，至少比磁盘的寻址加载速度要快。所以我们的建议是多内存少磁盘，这也是我们为什么要用B树来存储索引的原因。

小伙伴们有没有发现，磁盘的加载次数，基本上和树的高度相关联，高度越高，加载次数越多，反之亦然。

B树和B+树，在面试中还是可能会被问到的。

所以要掌握这两种树的应用和原理是很重要的，但也不如特别深入，理解即可，毕竟是找工作应付面试的（手动狗头）

下次再开始说下关于二叉树的概念，哈哈哈哈

我是狗子

祝你幸福