当前位置：首页 > news >正文

高阶数据结构--B树B+树实现原理B树模拟实现--Java

news 来源：原创 2025/6/30 20:09:47

一、B-树概念

二、B-树插入分析

1.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

2.插入过程总结

三、B树插入实现

四、B+树

1.B+树概念

2.B+树的特性

五、B+树应用

1.索引

2.Mysql索引

3.InnoDB

一、B-树概念

1970 年， R.Bayer 和 E.mccreight 提出了一种适合外查找的树，它是一种平衡的多叉树，称为 B 树 ( 有些地方写的是 B- 树，注意不要误读成"B 减树 ") 。一棵 M 阶 (M>2) 的 B 树，是一棵平衡的 M 路平衡搜索树，可以是空树 或者满足一下性质：

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

2. 每个非根节点至少有 M/2-1( 上取整 ) 个关键字 , 至多有 M-1 个关键字，并且以升序排列

例如：当 M=3 的时候，至少有 3/2=1.5 ，向上取整等于 2 ， 2-1=1 个关键字，最多是 2 个关键字

3. 每个非根节点至少有 M/2( 上取整 ) 个孩子 , 至多有 M 个孩子

例如：当 M=3 的时候，至少有 3/2=1.5 ，向上取整等于 2 个孩子。最多有 3 个孩子。

4. key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i] 、 key[i+1] 之间

5. 所有的叶子节点都在同一层

二、B-树插入分析

为了简单起见，假设 M = 3. 即 三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三个部分，因此节点 应该有三个孩子 ，为了后续实现简单期间，节点的结构如下：

注意：孩子永远比数据多一个。

插入过程当中，有可能需要分裂，分裂的前提是：

假设，当前是要组成一个M路查找树，关键字数必须<=M-1（这里关键字数>M-1就要进行节点拆分）规则是：把中间的元素，提取出来，放到父亲节点上，左边的单独构成一个节点，右边的单独构成一个节点。

1.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

2.插入过程总结

1. 如果树为空，直接插入新节点中，该节点为树的根节点

2. 树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)

3. 检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)

4. 按照插入排序的思想将该元素插入到找到的节点中

5. 检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足

6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：

(1申请新节点

(2找到该节点的中间位置

(3将该节点中间位置右侧的元素以及其孩子搬移到新节点中

(4将中间位置元素以及新节点往该节点的双亲节点中插入，即继续4

7. 如果向上已经分裂到根节点的位置，插入结束

三、B树插入实现

public class MyBTree {public static final int M=3;//三叉树static class BTreeNode {public int[] keys;//关键字public BTreeNode[] subs;//孩子节点public BTreeNode parent;//父节点public int UsedSize;//存储的关键字数量public BTreeNode() {//这里多给一个空间是为了分裂实现更容易keys=new int[M];subs=new BTreeNode[M+1];}}public BTreeNode root;/*** 插入一个元素* @param val*/public boolean insert(int val) {//B树为空的时候if(root==null) {root=new BTreeNode();root.keys[0]=val;root.UsedSize=1;return true;}//当B树不为空的时候Pair<BTreeNode,Integer> pair=Find(val);if(pair.getVal()!=-1) {return false;}BTreeNode parent=pair.getKey();int index=parent.UsedSize-1;for(;index>=0;index--) {if(parent.keys[index]>=val) {parent.keys[index+1]=parent.keys[index];}else {break;}}parent.keys[index+1]=val;parent.UsedSize++;if(parent.UsedSize>=M) {split(parent);return true;}else {return true;}}/*** 分裂节点* @param cur*/private void split(BTreeNode cur) {BTreeNode parent=cur.parent;BTreeNode newNode=new BTreeNode();int mid= cur.UsedSize>>1;int i=mid+1;int j=0;while (i<cur.UsedSize) {newNode.keys[j]=cur.keys[i];newNode.subs[j]=cur.subs[i];if(newNode.subs[j]!=null) {newNode.subs[j].parent=newNode;}i++;j++;}newNode.subs[j]=cur.subs[i];if(newNode.subs[j]!=null) {newNode.subs[j].parent=newNode;}newNode.UsedSize=j;cur.UsedSize=cur.UsedSize-j-1;if(cur==root) {root=new BTreeNode();root.keys[0]=cur.keys[mid];root.subs[0]=cur;root.subs[1]=newNode;root.UsedSize=1;cur.parent=root;newNode.parent=root;return;}newNode.parent=parent;int endT=parent.UsedSize-1;for (;endT>=0;endT--) {if(parent.keys[endT]>=cur.keys[mid]) {parent.keys[endT+1]=parent.keys[endT];parent.subs[endT+2]=parent.subs[endT+1];}else {break;}}parent.keys[endT+1]=cur.keys[mid];//将当前父亲节点的孩子节点更改为newNodeparent.subs[endT+2]=newNode;parent.UsedSize++;if(parent.UsedSize>=M) {split(parent);}}/*** 查找B树中是否存在该元素* @param val* @return*/private Pair<BTreeNode, Integer> Find(int val) {BTreeNode cur=root;BTreeNode parent = null;while (cur!=null) {int i=0;while (i<cur.UsedSize) {if(cur.keys[i]==val) {return new Pair<>(cur,i);} else if (cur.keys[i]<val) {i++;}else {break;}}parent=cur;cur=cur.subs[i];}return new Pair<>(parent,-1);}/*** 验证B树，如果输出的是一个有序的结果则证明是B树* @param root*/private void inorder(BTreeNode root){if(root == null)return;for(int i = 0; i < root.UsedSize; ++i){inorder(root.subs[i]);System.out.println(root.keys[i]);}inorder(root.subs[root.UsedSize]);}
}

B树验证

public static void main(String[] args) {MyBTree bTree=new MyBTree();int[] arrays={75,49,36,53,101,139,145};for (int i = 0; i < arrays.length; i++) {bTree.insert(arrays[i]);}bTree.inorder(bTree.root);}

输出结果：

四、B+树

1.B+树概念

B+树是B-树的变形，也是一种多路搜索树：

1. 其定义基本与B-树相同，除了：

2. 非叶子节点的子树指针与关键字个数相同

3. 非叶子节点的子树指针p[i]，指向关键字值属于【k[i]，k[i+1])的子树

4. 为所有叶子节点增加一个链指针

5. 所有关键字都在叶子节点出现

B+树的搜索与B-树基本相同，区别是B+树只有达到叶子节点才能命中(B-树可以在非叶子节点中命中)，其性能也等价与在关键字全集做一次二分查找。

2.B+树的特性

1. 所有关键字都出现在叶子节点的链表中(稠密索引)，且链表中的节点都是有序的。

2. 不可能在非叶子节点中命中。

3. 非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储数据的数据层。

4. 更适合文件索引系统

五、B+树应用

1.索引

B+树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，比如：书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构。

MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构。当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引。

2.Mysql索引

MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下：

上图是以以 Col1 为主键， MyISAM 的示意图，可以看出 MyISAM 的索引文件仅仅保存数据记录的地址 。在 MyISAM 中，主索引和辅助索引（ Secondary key ）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复 。如果想在 Col2 上建立一个辅助索引，则此索引的结构如下图所示：

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

3.InnoDB

InnoDB 存储引擎支持事务 ，其设计目标主要面向在线事务处理的应用，从 MySQL 数据库 5.5.8 版本开始， InnoDB 存储引擎是默认的存储引擎 。 InnoDB 支持 B+ 树索引、全文索引、哈希索引。但 InnoDB 使用 B+Tree 作为索引结构时，具体实现方式却与MyISAM 截然不同。

第一个区别是 InnoDB 的数据文件本身就是索引文件 。 MyISAM 索引文件和数据文件是分离的，索引文件仅保存数 据记录的地址 。而 InnoDB 索引，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保 存了完整的数据记录 。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

上图是 InnoDB 主索引 （同时也是数据文件）的示意图，可以看到 叶节点包含了完整的数据记录，这种索引叫做聚 集索引 。因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键 （ MyISAM 可以没有），如果 没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键 ， 如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整形 。

第二个区别是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址 , 所有辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索十分高效 ，但是 辅助索引搜索需要检索两遍索引：首先检索辅助索引获得 主键，然后用主键到主索引中检索获得记录。

一、B-树概念

二、B-树插入分析

1.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

2.插入过程总结

三、B树插入实现

四、B+树

1.B+树概念

2.B+树的特性

五、B+树应用

1.索引

2.Mysql索引

3.InnoDB

相关文章：