[Collection与数据结构] B树与B+树

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (93平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀线程与网络(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
🍃 Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
🎃Redis(97平均质量分)https://blog.csdn.net/2301_80050796/category_12777129.html?spm=1001.2014.3001.5482
🐰RabbitMQ(97平均质量分) https://blog.csdn.net/2301_80050796/category_12792900.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~

1. 常见的基本搜索结构

以上的结构适合用于数量不是很大的情况,如果数量非常巨大,一次性无法加载到内存中,使用上述结构就不是很方便,比如: 使用平衡树搜索一个大文件.

上面方法其实只在内存中保存了每一项数据信息中需要查询的字段以及数据在磁盘中的位置,整体的数据实际也在磁盘中.
缺陷:

1. 树的高度比较高,查找的时候最差情况之下要比较树的高度次.
2. 数据量如果特别大的时候,树的结点可能无法一次性加载到内存中,需要多次硬盘IO,这时候就会拖慢查找的速度.
   那如何提高对数据访问的速度呢?
3. 提高IO的速度
4. 降低树的高度,即使用多叉平衡树.

2. B树的概念

B树是一种平衡的多叉树,称为B树(有些地方可能写的是B-树,注意不要读作"B减数").一棵M阶(M>2)的B树,是一棵平衡的M路搜索平衡搜索树,可以是空树或者满足一下的性质:

1. 根结点至少有两个孩子
2. 每个非根结点至少有M/2-1(向上取整)个关键字,至多有M-1个关键字,并且以升序的方式排列.
3. 每个非根节点至少有M/2(向上取整)个孩子,至多有M个孩子.
4. 孩子结点永远比关键字多一个.
   
5. key[i]和key[i+1]之间的孩子结点的值介于key[i],key[i+1]之间.
6. 所有的叶子结点都在同一层.

非根节点中至少有M/2-1(向上取整)个关键字和M/2(向上取整)个孩子是因为在每次节点满了之后都会拷走一半,这和节点的分裂有关,我们后续介绍.

3. B树的插入分析

为了简单起见,假设M=3,即是一棵三叉树,每个节点中保存两个数据,两个数据可以将区间分为三个部分,因此结点应该有三个孩子,为了后续实现简单起见,结点的结构如下.上一层存储的书该结点的数据,下一层存储的是孩子结点的地址.

我们之前规定的是3叉树,这里之所以要把4叉树当做3叉树来看待是因为数据满了之后,需要先进行插入再进行分裂,如果数据只有两个存储空间的话,新数据无法插入结点,也就无法正常进行分裂.下面我们来解释一下结点的分裂:

在我们插入的过程当中,有可能结点是需要分裂的.
前提是:
当前这棵树是一个M叉树,当一个关键字插入之后,关键字数目>M-1就要对结点进行拆分.拆分的规则是,把中间的元素提出来,放到父节点上(如果分裂的是根结点,则父节点不存在,需要新建一个结点),中间元素左边的的元素单独构成一个结点(保留在原来的结点中),中间元素右边的元素单独构成一个结点(这个结点一半不存在,需要新建).
比如我们使用53,139,75,49,145,36,101构建B树的过程如下:





这里我们发现,B树的分裂是横向的分裂,新老结点在同一层,也就是不会使得树的高度增加,正是因为结点的横向分裂,所以B树才是天然平衡的.只有在分裂根节点的时候,高度才会增加.


注意在对根节点分裂的时候,139的两个孩子结点也要跟着139这个结点一起复制过来.

插入过程总结:

1. 如果树为空,直接插入新结点中,该结点为树的根节点.
2. 树非空,找待插入元素在树中的位置(注意:找到插入结点的位置一定在叶子结点上)
3. 树中的key唯一,即该元素已经存在的时候则不插入.
4. 按照插入顺序的思想将该元素插入到找到的结点中
5. 检测该结点是否满足B树的性质: 即该结点中的元素个数是否<=M-1.
6. 如果插入结点后结点不满足B树的性质,需要对该结点进行分裂:
   • 申请新的结点
   • 找到该结点的中间位置
   • 将该结点的中间位置右侧的元素以及其孩子搬移到新结点中.
   • 将中间位置元素以往该结点的双亲节点中插入.之后调整树的连接方式,把分裂出去的数据的孩子一起调整走.
7. 如果向上分裂已经到了根结点的位置,插入结束.
8. 如果更节点在插入之后也是满的,则要继续重复上述步骤分裂根节点.

4. B树的插入实现

4.1 B树的结点设计

结点需要包含这几部分:

• 一个是存储数据的数据域
• 一个是存储孩子结点的地址域
• 为了方便分裂中中间元素向上插入,我们还要记录当前结点的双亲节点.
• 记录有效数据的size.
• 最后在给构造方法的时候注意要多给一个数据域和指针域.

public class BTreeNode {public int[] keys;//存储数据public BTreeNode[] subs;//存储孩子结点public BTreeNode parents;//存储双亲public int size;//有效数据个数public BTreeNode(int M){//M叉树this.keys = new int[M];//多给一个位置this.subs = new BTreeNode[M+1];this.size = 0;}
}

4.2 插入key的过程

• 首先判断该树是否是一棵空树,如果是空树,则需要新建一棵树,并让根节点数据域的第一个元素为key;
• 之后寻找该树中是否存在该数据,如果存在,直接返回,如果不存在,则继续下一步的插入逻辑
• 在最终找到的叶子结点中进行数据的插入
• 看看叶子结点是否为满
• 如果满了,需要进行下一步的分裂操作.

我们在判断结点中是否存在指定的值的时候,如果直接返回一个结点,我们无法判断直接判断这个节点返回的是未找到数据最终到达的叶子结点还是找到数据的结点,所以我们必须通过一个Integer来标记这个数据是否真的存在.我们定义一种数据类型叫做Pair,前面存放结点,后面存放整形以判断这个值是否存在.

//键值对
public class Pair <K,V>{public K key;public V val;public Pair(K key, V val) {this.key = key;this.val = val;}
}

插入逻辑

public class Insert {public BTreeNode root;//定义根节点public final int M = 3;//定义的是一个三叉树public boolean insert(int key){//查看root是否为空if (root == null){root = new BTreeNode(M);root.keys[0] = key;root.size = 1;return true;}//接下来寻找元素在树中是否存在Pair<BTreeNode,Integer> pair = find(key);//如果返回的不是-1,证明是存在的if (pair.val != -1){return false;}BTreeNode cur = pair.key;//拿到当前结点之后进行数据插入int index = cur.size-1;for (;index > 0;index--){if (cur.keys[index] > key){cur.keys[index+1] = cur.keys[index];} else if (cur.keys[index] < key) {break;}}cur.keys[index+1] = key;cur.size++;//之后查看是否需要分裂节点if (cur.size < M){return true;//不需要分裂,直接返回}else {split(cur);//不满足B树性质,需要分裂return true;}}/*** 寻找key在树中是否存在* @param key 需要寻找的key* @return 返回键值对*/private Pair<BTreeNode,Integer> find(int key){BTreeNode cur = root;BTreeNode parent = null;while (cur != null){//在整棵树中遍历int i = 0;while (i != cur.size){//在当前结点中遍历if (cur.keys[i] == key){return new Pair<>(cur,cur.keys[i]);}else if (cur.keys[i] < key){i++;}else {break;}}parent = cur;//如果最后没有找到,parent记录的是叶子结点cur = cur.subs[i];//如果最后没有找到,这个结点记录的是null}//走到了最后证明没有找到return new Pair<>(parent,-1);}/*** 分裂当前结点* @param cur 需要分裂的结点*/private void split(BTreeNode cur){BTreeNode newNode = new BTreeNode(M);//保存中间数据右边数据的结点BTreeNode parent = cur.parents;//记录该结点的父节点,把中间的数据提到父节点上去int mid = cur.size/2;int j = 0;int i = mid+1;for (;i < cur.size;i++){newNode.keys[j] = cur.keys[i];//数据复制走newNode.subs[j] = cur.subs[i];//孩子一起复制走//如果孩子不为空,就把孩子的父亲改成newNodeif (newNode.subs[j] != null){newNode.subs[j].parents = newNode;}j++;}//孩子还需要再复制一次newNode.keys[j] = cur.keys[i];//数据复制走newNode.subs[j] = cur.subs[i];//孩子一起复制走//如果孩子不为空,就把孩子的父亲改成newNodeif (newNode.subs[j] != null){newNode.subs[j].parents = newNode;}//更改newNode的size和原结点的sizenewNode.size = j;cur.size = cur.size-j-1;//包括复制走的数据和提到父节点上的数据if (cur.parents == null){//如果该结点是根结点root = new BTreeNode(M);root.keys[0] = cur.keys[mid];root.subs[0] = cur;cur.parents = root;root.subs[1] = newNode;newNode.parents = root;root.size = 1;return;}//如果该结点不是根结点newNode.parents = parent;int end = parent.size-1;int midVal = cur.keys[mid];//进行数据的插入for (;end > 0;end--){if (parent.keys[end] > midVal){parent.keys[end+1] = parent.keys[end];parent.subs[end+2] = parent.subs[end+1];//把数据和孩子都复制过去}else if (parent.keys[end] < midVal){break;}}parent.keys[end+1] = midVal;//把中间值移动过来parent.subs[end+2] = newNode;//把新节点连接到root上parent.size++;if (parent.size >= M){//如果根结点满了,继续分裂split(parent);}}
}

4.4 B树的性能分析

对于一棵结点为N度为M的B树,查找和插入需要log_M-1N到log_M/2N次比较,证明如下:对于度为M的B树,每个节点的子节点个数为M/2到(M-1)之间,因此树的高度应该要在log_M-1N和log_M/2N之间,在定位到该节点之后,每个节点中的数据个数一般非常有限,再采用二分查找的方式可以很快定位到该元素,时间复杂度可以近似看做O(1).
B-树的效率是很高的,对于N = 62*1000000000个节点,如果度M为1024,则
log_M/2N<= 4,即在620亿个元素中,如果这棵树的度为1024,则需要小于4次即可定位到该节点,然后利用二分查找可以快速定位到该元素,大大减少了读取磁盘的次数.

4.5 B树的删除

参考<<算法导论>>或者<<数据结构-严蔚敏版>>.

5. B+树和B*树

5.1 B+树

B+树为B树的升级版,也是一种多路搜索树,它通常被用于数据库中建立索引以加快查找的速度.我们在MySQL的索引章节也有所介绍.
B+树的性质如下:

1. 非叶子结点的子树指针域的个数和关键字的个数相同.
2. 非叶子结点的子树指针p[i],指向关键字属于[k[i],k[i+1])的子树.也就是它的孩子中一定存在一个元素k[i].
3. 为所有叶子结点增加一个链指针.把所有的叶子结点都串联起来,都指向自己的下一个兄弟节点,是一个链表,且链表中的节点数据都是有序的.
4. 所有的真正的数据都在叶子结点出现.非叶子结点的关键字不是实际的数据记录,而是一种索引信息,用来引导搜索路径.
5. 查找的次数相对于B树来说更加稳定,因为不管数据是多少,每次都要遍历到叶子结点.

B+树的搜索方式与B树基本相同,区别是B+树只有到达叶子结点才会命中数据,而B树有可能在非叶子结点就可以命中.
下面是B+树的分裂方式:
首先是叶子结点分裂:

• 当一个结点满的时候,分配一个新的结点,并将原结点中1/2的数据(较大的那1/2)复制到新的结点
• 原结点的下一个兄弟节点的指针指向新的结点.
• 更新父节点的指针信息,使得父节点正确指向分裂之后的两个结点.

其次是非叶子结点的分裂:

• 当为叶子结点插入数据的操作导致某个非叶子结点满,就需要对非叶子结点进行分裂.
• 对于非叶子结点,同样选择中间的位置进行分裂,它左边的键值和指针留在原节点,右边的键值和指针移动到新节点.
• 更新父节点的指针信息,使得父节点正确指向分裂之后的两个结点.
• 如果父节点满,则继续上述的步骤,直到不再产生分裂或者是到根节点
• 如果根节点发生了分裂,则创建一个新的根节点,将原根节点分裂后的两个节点作为新根节点的子节点,将分裂点键值放入新根节点.

5.2 B*树

B*树是B+树的变形,在B+树的非根和非叶子结点在增加了指向兄弟节点的指针.

分裂方式如下:
当一个结点满的时候,如果他的下一个兄弟节点未满,那么将一部分数据移动到他的兄弟节点中,再在原结点中插入关键字,最后修改父节点中兄弟节点的关键字(兄弟节点的数据发生了改变).如果兄弟节点也满了,则需要进行分裂,这里和B+树类似,不再赘述,唯一不同的是在非叶子结点分裂的时候,也需要修改兄弟节点指针的指向.