java面试问以后的规划（Java面试常见问题B-树和B）

java面试问以后的规划（Java面试常见问题B-树和B）B 树（M=3）B 树是B-树的一种变形，其与B-树的区别主要在于：B-树需要满足以下规则：另外B-树的每个结点，除了有关键字key以外，还有value，也就是关键字记录的指针（地址）。苹果电脑的HFS 文件系统，就采用了B树作为文件系统的索引。

除了Java语法和并发编程方面这些必考内容，Java面试还经常会问到关于数据结构方面的问题。本文就来介绍两个在数据库和文件系统中常用的数据结构：B-树和B 树。需要注意的是：“B-树”中的短横不是减号，B表示平衡（Balance）的意思。

B-树

B-树是为了磁盘或其它存储设备而设计的一种平衡多叉搜索树。B-树与平衡二叉搜索树最大的不同在于，B-树的结点可以有许多孩子。B-树可以在O（logn）的时间复杂度内，实现插入、删除等动态操作，相比平衡二叉树，大大减少了IO的次数。

B-树（M=3）

M阶B-树（M>2），代表一个树结点最多有M个子结点（查找路径），上图为3阶B-树。

B-树需要满足以下规则：

• 排序方式：每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它；
• 子结点数：根结点的子结点数为[2 M]，其他非叶结点的子结点数为[M/2 M]，向上取整；
• 关键字数：非叶结点的关键字数量为子结点数-1，如上图每个非叶结点有2个关键字，分成3个区间，分别指向3个子树；
• 叶子结点：所有叶子结点均在同一层，或者说根节点到每个叶子节点的长度都相同；

另外B-树的每个结点，除了有关键字key以外，还有value，也就是关键字记录的指针（地址）。

苹果电脑的HFS 文件系统，就采用了B树作为文件系统的索引。

B 树

B 树是B-树的一种变形，其与B-树的区别主要在于：

• 非叶子结点的子树指针与关键字个数相同；
• 非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i] K[i 1]) 的子树，而B-树的子树结点关键字不包括 K[i]；
• 所有叶子结点增加了一个链指针；
• 所有关键字都在叶子结点出现。

B 树（M=3）

上图是一个 M=3 的 B 树，非叶子结点的关键字个数和子树指针都是3个。第一个非叶子结点（5，10，20）的第一个指针 P1 指向的子树，只有一个叶子结点，P1对应的关键字5又出现在了叶子结点的关键字中。

B 树的应用

B 树适合应用于操作系统的文件索引和数据库索引。B 树相比于B树，在文件系统和数据库系统当中更有优势，原因如下：

1. IO读写代价低
   B 树的非叶结点不保存关键字记录的指针，只进行数据索引，B 树每个非叶节点所能保存的关键字大大增加。一次性读入内存中的关键字越多，也就意味着I/O读写次数越少。
2. 查询效率稳定
   B 树只有叶子结点保存了关键字记录的指针，任何关键字记录的查找都必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，数据查询效率相比B-树更加稳定。
3. 有利于数据库扫描
   B 树只需要遍历叶子结点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的区间查询，B 树有着更高的性能。

基于B 树的Mysql数据库索引

Mysql的InnoDB和MylSAM存储引擎都是用B 树实现索引结构。

我会持续更新关于物联网、云原生以及数字科技方面的文章，用简单的语言描述复杂的技术，也会偶尔发表一下对IT产业的看法，欢迎大家关注、转发和评论。