B-树

前面我们已经学习了二叉查找树,2-3树以及它的实现红黑树,2-3树中,一个节点最多能有两个key,它的实现在红黑树中是用对链接染色的方式去表达这两个key,接下来我们学习另外一种树形结构B树,这种数据结构中,一个节点允许多于两个key的存在

B树是一种树状数据结构,它能够存储数据,对其进行排序并允许以$O(logn)$的时间复杂度进行查找,顺序读取,插入和删除等操作

B树的特性

B树中允许一个节点中包含多个key,可以是3个,4个,5个甚至更多,并不确定,需要看具体的实现,现在我们选择一个参数M,来构造一个B树,我们可以把它称作是M阶的B树,那么该树会具有如下特点:

  • 每个节点最多有M-1个key,并且以升序排序
  • 每个节点最多能有M个子节点
  • 根节点至少有两个子节点

在实际应用中B树的阶数一般都比较大(通常大于100),所以即使存储大量的数据,B树的高度仍然比较小,这样在某些应用场景下,就可以体现出它的优势

B树存储数据

若参数M选择为5,那么每个节点最多包含4个键值对,我们以5阶B树为例,看看B树的数据存储

B树在磁盘文件中的应用

在我们的程序中,不可避免的需要通过IO操作文件,而我们的文件是存储在磁盘上的,计算机操作磁盘上的文件是通过文件系统进行操作的,在文件系统中就使用到了B树这种数据结构

磁盘

磁盘能保存大量的数据,从GB一直到TB级,但是他的读取速度比较慢,因为涉及到机器操作,读取速度为毫秒级

磁盘由盘片构成,每个盘片有两面,又称为盘面,盘片中央有一个可以旋转的主轴,他使得盘片以固定的旋转速率旋转,通常是5400rpm或者是7200rpm,一个磁盘中包含了多个这样的盘片并封装在一个密封的容器内,盘片的每个表面是由一组称为磁道同心圆组成的,每个磁道被划分为了一组扇区,每个扇区包含相等数量的数据位,通常是512个字节,扇区之间由一些间隙隔开,这些间隙中不存储数据

磁盘IO

磁盘用磁头来读写存储在盘片表面的位,而磁头连接到一个移动臂上,移动臂沿着盘片半径前后移动,可以将磁头定位到任何磁道上,这称之为寻道操作,一旦定位到磁道后,盘片转动,磁道上的每个位经过磁头时,读写磁头就可以感知到该位的值,也可以修改值,对磁盘的访问时间分为寻道时间,旋转时间以及传送时间

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动消费,因此为了提高效率,要尽量减少磁盘$I/O$,减少读写操作,为了达到这个目的,磁盘往往不是严格按需读取而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存,这样做的理论依据是计算机科学中很著名的局部性原理:当一个数据被用到时,其附近的数据也通常会被马上使用掉,由于磁盘顺序读取的效率很高(不需要寻道时间,只需要很少的旋转时间),因此预读可以提高$I/O$效率

页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(1024个字节或其整数倍),预读的长度一般为页的整数倍,主存和磁盘以页为单位交换数据,当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或者几页载入内存中,然后异常返回,程序继续运行

文件系统的设计者利用了磁盘预读原理,将一个节点的大小设为等于一个页(1024个字节或其整数倍),这样每个节点只需要一次$I/O$就可以完全载入,那么3层的B树可以容纳$1024*1024*1024$差不错10亿个数据,如果换成二叉查找树,则需要30层,假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在10亿个数据中查找目标值,只需要小于3次硬盘读取就可以找到目标值,但红黑树需要小于30次,因此B树大大提高了IO的操作效率

B+树

B+树是对B树的一种变形树,它与B树的差异在于

  1. 非叶节点仅具有索引作用,也就是说非叶子节点值存储key,不存储value
  2. 树的所有叶节点构成一个有序链表,可以按照key排序的次序遍历全部数据

B+树存储数据

若参数M选择为5,那么每个节点最多包含4个键值对,我们以5阶B+树为例,看看B+树的数据存储

B+树和B树的对比

$$ B+树的优点: $$

  1. 由于B+树在非叶子节点上不包含真正的数据,只当做索引使用,因此在内存相同的情况下,能够存放更多的key
  2. B+树的叶子节点都是相连的,因此对整棵树的遍历只需要一次线性遍历叶子节点即可,而且由于数据顺序排列并且相连,所以便于区间查找和搜索,而B树则需要进行每一层的递归遍历

$$ B树的优点: $$

  1. 由于B树的每一个节点都包含key和value,因此我们根据key查找value时,只需要找到key所在的位置,就能找到value,但B+树只有叶子节点存储数据,索引每一次查找,都必须一次一次查找,一直找到树的最大深度处,也就是叶子节点的深度,才能找到value

B+树在数据库中的应用

在数据库的操作中,查询操作可以说是最频繁的一种操作,因此在设计数据库时,必须要考虑到查询的效率问题,在很多数据库中,都是用到了B+树来提高查询的效率

在操作数据库时,我们为了提高查询效率,可以基于某张表的某个字段建立索引,就可以提高查询效率,那其实这个索引就是B+树这种数据结构的实现

未建立主键索引查询

执行select * from user where id='18'需要从第一条数据开始,一直查询到第6条,发现id=18,此时才能查询出目标结果,共需要比较6次

建立主键索引查询

区间查询

执行select * from user where id > 12 and id < 18,如果有了索引,由于B+树的叶子节点形成了一个有序链表,所以我们只需要找到id为12的叶子节点,按照遍历链表的方式顺序往后查找即可,效率非常高

并查集

并查集是一种树型的数据结构,并查集可以高效地进行如下操作:

  • 查询元素p和元素q是否属于同一组
  • 合并元素p和元素q所在的组

并查集结构

并查集也是一种树形结构,但这棵树跟我们之前讲的二叉树,红黑树,B树等都不一样,这种树的要求比较简单:

  1. 每个元素都唯一的对应一个节点
  2. 每一组数据中的多个元素都在同一棵树中
  3. 一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系
  4. 元素在树中并没有子父级关系的硬性要求

并查集API设计

类名UF
构造方法UF(int N):初始化并查集,以整数标识(0,N-1)个节点
成员方法1.public int count():获取当前并查集中的数据有多少个分组 2.public boolean connected(int p,int q):判断并查集中元素p和元素q是否在同一分组中 3.public int find(int p):元素p所在分组的标识符 4.public void union(int p,int q):把p元素所在分组和q元素所在分组合并
成员变量1.private int[] eleAndGroup:记录节点元素和该元素所在分组的标识 2.private int count:记录并查集中数据的分组个数

并查集的实现

UF(int N)结构方法实现

  1. 初始情况下,每个元素都在一个独立的分组中,所以初始情况下,并查集中的数据默认分为N个组
  2. 初始化数组eleAndGroup
  3. 把eleAndGroup数组的索引看作是每个节点存储的元素,把eleAndGroup数组每个索引处的值看做是该节点所在的分组,那么初始化情况下,i索引处存储的值就是i

union(int p,int q)合并方法实现

  1. 如果p和q已经在同一个分组中,则无需合并
  2. 如果p和q不在同一个分组,则只需要将p元素所在组的所有元素的组标识符修改为q元素所在组的标识符即可
  3. 分组数量-1

代码实现

UF

public class UF {

  /**
   * 记录节点元素和该元素所在分组的标识
   */
  private int[] eleAndGroup;
  /**
   * 记录并查集中数据的分组个数
   */
  private int count;

  /**
   * 初始化并查集
   */
  public UF(int N) {
    //初始化分组的数量,默认情况下初始化N个分组
    this.count = N;
    //初始化eleAndGroup数组
    this.eleAndGroup = new int[N];
    //初始化eleAndGroup中的元素及其所在组的标识符
    for (int i = 0; i < eleAndGroup.length; i++) {
      eleAndGroup[i] = i;
    }
  }

  /**
   * 获取当前并查集中的数据有多少个分组
   */
  public int count() {
    return count;
  }

  /**
   * 元素p所在分组的标识符
   */
  public int find(int p) {
    return eleAndGroup[p];
  }

  /**
   * 判断并查集中元素p和元素q是否在同一分组
   */
  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }

  /**
   * 把p元素所在分组和q元素所在分组合并
   */
  public void union(int p, int q) {
    //判断元素p与q是否已经在同一分组中
    if (connected(p, q)) {
      //如果在在同一分组中,则直接结束方法
      return;
    } else {
      //如果不在同一分组,则将两个分组合并
      //先找到p所在分组的标识符
      int pGroup = find(p);
      //再找到q所在分组的标识符
      int qGroup = find(q);
      //合并组,让p所在组的所有元素的组标识符变为q所在分组的标识符
      for (int i = 0; i < eleAndGroup.length; i++) {
        if (eleAndGroup[i] == pGroup) {
          eleAndGroup[i] = qGroup;
        }
      }
      //分组个数-1
      this.count--;
    }
  }
}

UFTest

public class UFTest {

  public static void main(String[] args) {
    //创建并查集对象
    UF uf = new UF(5);
    System.out.println("默认情况下,并查集有的组数:" + uf.count());
    //从控制台录入两个要合并的元素,调用union方法进行合并,观察合并后并查集中的分组是否变少
    Scanner sc = new Scanner(System.in);
    while (true) {
      System.out.println("请输入第一个要合并的元素:");
      int p = sc.nextInt();
      System.out.println("请输入第二个要合并的元素");
      int q = sc.nextInt();
      //判断这两个元素是否已经在同一组了
      if (uf.connected(p, q)) {
        System.out.println(p + "元素和" + q + "已经在同一组了");
        continue;
      } else {
        uf.union(p, q);
        System.out.println("当前并查集的组的个数:" + uf.count());
      }
    }
  }
}

并查集应用举例

如果我们并查集存储的每一个整数表示的是一个大型计算机网络中的计算机,则我们就可以通过connected(int p,int q)来检测,该网络中的某两台计算机之间是否连通,如果连通,则他们之间可以通信,如果不连通,则不能通信,此时我们又可以调用union(int p,int q)使得p和q之间连通,这样两台计算机之间就可以通信了

一般像计算机这样网络型的数据,我们要求网络中的每两个数据之间都是相连通的,也就是说,我们需要调用很多次union方法,使得网络中所有数据相连,其实我们很容易可以得出,如果要让网络中的数据都相连,则我们至少要调用$N-1$次union方法才可以,但由于我们的union方法中使用for循环遍历了所有的元素,所以很明显,我们之前实现的合并算法的时间复杂度是$O(N^2)$,如果要解决大规模问题,它是不适合的,所以我们需要对算法进行优化

UF_Tree算法优化

为了提升union算法的性能,我们需要重新设计find方法和union方法的实现,此时我们先需要对我们之前数据结构中的eleAndGroup数组的含义重新设定

  1. 我们仍然让eleAndGroup数组的索引作为某个节点的元素
  2. eleAndGroup[i]的值不再是当前节点所在的分组标识,而是该节点的父节点

UF_Tree API设计

类名UF_Tree
构造方法UF_Tree(int N):初始化并查集,以整数标识(0,N-1)个节点
成员方法1.public int count():获取当前并查集中的数据有多少个分组 2.public boolean connected(int p,int q):判断并查集中元素p和元素q是否在同一分组中 3.public int find(int p):元素p所在分组的标识符 4.public void union(int p,int q):把p元素所在分组和q元素所在分组合并
成员变量1.private int[] eleAndGroup:记录节点元素和该元素的父节点 2.private int count:记录并查集中数据的分组个数

find(int p)查询方法实现

  1. 判断当前元素p的父节点和eleAndGroup[p]是不是自己,如果是自己则证明已经是根节点了
  2. 如果当前元素p的父节点不是自己,则让p=eleAndGroup[p],继续寻找父节点的父节点,直到找到根节点为止

union(int p,int q)合并方法实现

  1. 找到p元素所在树的根节点
  2. 找到q元素所在树的根节点
  3. 如果q和p已经在同一个树中,则无需合并
  4. 如果p和q不在同一个分组,则只需要将p元素所在树根节点的父节点设置为q元素的根节点即可
  5. 分组数量-1

代码实现

UF_Tree

public class UF_Tree {

  /**
   * 记录节点元素和该元素所在分组的标识
   */
  private int[] eleAndGroup;
  /**
   * 记录并查集中数据的分组个数
   */
  private int count;

  /**
   * 初始化并查集
   */
  public UF_Tree(int N) {
    //初始化分组的数量,默认情况下有N个分组
    this.count = N;
    //初始化eleAndGroup数组
    this.eleAndGroup = new int[N];
    //初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个节点的元素
    for (int i = 0; i < eleAndGroup.length; i++) {
      eleAndGroup[i] = i;
    }
  }

  /**
   * 获取当前并查集中的数据有多少个分组
   */
  public int count() {
    return count;
  }

  /**
   * 判断并查集中元素p和元素q是否在同一分组中
   */
  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }

  /**
   * 元素p所在分组的标识符
   */
  public int find(int p) {
    while (true) {
      if (eleAndGroup[p] == p) {
        return p;
      } else {
        p = eleAndGroup[p];
      }
    }
  }

  /**
   * 把p元素所在分组和q元素所在分组合并
   */
  public void union(int p, int q) {
    //找到p元素和q元素所在组对应的树的根节点
    int pRoot = find(p);
    int qRoot = find(q);
    //如果p和q已经在同一分组,则不需要合并了
    if (pRoot == qRoot) {
      return;
    }//如果不在同一分组,则需要合并
    else {
      //让p所在树的根节点的父节点成为q所在树的根节点即可
      eleAndGroup[pRoot] = qRoot;
      //组的数量-1
      this.count--;
    }
  }
}

UF_TreeTest

public static void main(String[] args) {
    //创建并查集对象
    UF_Tree uf = new UF_Tree(5);
    System.out.println("默认情况下,并查集有的组数:" + uf.count());
    //从控制台录入两个要合并的元素,调用union方法进行合并,观察合并后并查集中的分组是否变少
    Scanner sc = new Scanner(System.in);
    while (true) {
      System.out.println("请输入第一个要合并的元素:");
      int p = sc.nextInt();
      System.out.println("请输入第二个要合并的元素");
      int q = sc.nextInt();
      //判断这两个元素是否已经在同一组了
      if (uf.connected(p, q)) {
        System.out.println(p + "元素和" + q + "已经在同一组了");
        continue;
      } else {
        uf.union(p, q);
        System.out.println("当前并查集的组的个数:" + uf.count());
      }
    }
  }

优化后的性能分析

我们优化后的算法union,如果要把并查集中所有的数据连通,仍然至少要调用N-1次union方法,但是我们发现union方法中已经没有了for循环,所以union算法的时间复杂度有$O(N^2)$变味了$O(N)$

但是这个算法仍然有问题,因为我们之前不仅修改了union算法,还修改了find算法,我们修改前的find算法的时间复杂度在任何情况下都为$O(1)$,但修改后的find算法在最坏的情况下是$O(N)$

在union方法中调用了find方法,所以在最坏情况下union算法的时间复杂度仍然为$O(N^2)$

路径压缩

UF_Tree中最坏情况下union算法的时间复杂度为$O(N^2)$,其最主要的问题在于最坏情况下,树的深度和数组的大小一样,如果我们能够通过一些算法让合并时,生成的树的深度尽可能的小,就可以优化find方法

之前我们在union算法中,合并树的时候将任意的一棵树连接到了另一棵树上,这种合并方法是比较暴力的,如果我们把并查集中每一棵树的大小记录下来,然后在每次合并树的时候,把较小的树连接到较大的树上,就可以减少树的深度

只要我们保证每次合并,都能把小树合并到大树上,就能压缩合并后新树的路径,这样就能提高find方法的效率,为了完成这个需求,我们需要另外一个数组来记录存储每个根节点对应的树中元素的个数,并且需要一些代码调整数组中的值

UF_Tree_Weighted API设计

类名UF_Tree_Weighted
构造方法UF_Tree_Weighted(int N):初始化并查集,以整数标识(0,N-1)个节点
成员方法1.public int count():获取当前并查集中的数据有多少个分组 2.public boolean connected(int p,int q):判断并查集中元素p和元素q是否在同一分组中 3.public int find(int p):元素p所在分组的标识符 4.public void union(int p,int q):把p元素所在分组和q元素所在分组合并
成员变量1.private int[] eleAndGroup:记录节点元素和该元素的父节点 2.private int[] size:存储每个根节点对应的树中元素的个数 3.private int count:记录并查集中数据的分组个数

代码实现

UF_Tree_Weighted

public class UF_Tree_Weighted {

  /**
   * 记录节点元素和该元素所在分组的标识
   */
  private int[] eleAndGroup;
  /**
   * 记录并查集中数据的分组个数
   */
  private int count;
  /**
   * 用来存储每一个根节点对应的树中保存的节点个数
   */
  private int[] size;

  /**
   * 初始化并查集
   */
  public UF_Tree_Weighted(int N) {
    //初始化分组的数量,默认情况下有N个分组
    this.count = N;
    //初始化eleAndGroup数组
    this.eleAndGroup = new int[N];
    //初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个节点的元素
    for (int i = 0; i < eleAndGroup.length; i++) {
      eleAndGroup[i] = i;
    }
    //默认情况下,size中每个索引的值都是1
    this.size = new int[N];
    for (int i = 0; i < size.length; i++) {
      size[i] = 1;
    }
  }

  /**
   * 获取当前并查集中的数据有多少个分组
   */
  public int count() {
    return count;
  }

  /**
   * 判断并查集中元素p和元素q是否在同一分组中
   */
  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }

  /**
   * 元素p所在分组的标识符
   */
  public int find(int p) {
    while (true) {
      if (eleAndGroup[p] == p) {
        return p;
      } else {
        p = eleAndGroup[p];
      }
    }
  }

  /**
   * 把p元素所在分组和q元素所在分组合并
   */
  public void union(int p, int q) {
    //找到p元素和q元素所在组对应的树的根节点
    int pRoot = find(p);
    int qRoot = find(q);
    //如果p和q已经在同一分组,则不需要合并了
    if (pRoot == qRoot) {
      return;
    }//如果不在同一分组,则需要合并
    else {
      //判断pRoot对应的树深还是qRoot对应的树深,最终需要把较小的树合并到较大的树中
      if (size[pRoot] < size[qRoot]) {
        eleAndGroup[pRoot] = qRoot;
        size[qRoot] += size[qRoot];
      } else {
        eleAndGroup[qRoot] = pRoot;
        size[pRoot] += size[qRoot];
      }
      //组的数量-1
      this.count--;
    }
  }
}

UF_Tree_WeightedTest

public static void main(String[] args) {
    //创建并查集对象
    UF_Tree_Weighted uf = new UF_Tree_Weighted(5);
    System.out.println("默认情况下,并查集有的组数:" + uf.count());
    //从控制台录入两个要合并的元素,调用union方法进行合并,观察合并后并查集中的分组是否变少
    Scanner sc = new Scanner(System.in);
    while (true) {
      System.out.println("请输入第一个要合并的元素:");
      int p = sc.nextInt();
      System.out.println("请输入第二个要合并的元素");
      int q = sc.nextInt();
      //判断这两个元素是否已经在同一组了
      if (uf.connected(p, q)) {
        System.out.println(p + "元素和" + q + "已经在同一组了");
        continue;
      } else {
        uf.union(p, q);
        System.out.println("当前并查集的组的个数:" + uf.count());
      }
    }
  }

案例-畅通工程

某省调查城镇交通情况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇,省政府畅通工程的目标是使全省任何两个城镇之间都可以实现交通出行(但不一定有直接连接的道路,只要互相间接通过道路到达即可),问最少还需要建设多少条道路

测试数据文件夹中有一个traffic_project.txt文件,它就是城镇道路统计表,下面是对数据的解释

总共有20个城市,目前已经修改好了7条道路,问还需要修建多少条道路,才能让这20个城市之间全部相连通

解题思路

  1. 创建一个并查集UF_Tree_Weighted(20)
  2. 分别调用union(0,1),union(6,9),union(3,8),union(5,11),union(2,12),union(6,10),union(4,8)表示已经修建好的道路把对应的城市连接起来
  3. 如果城市全部连接起来,那么并查集中剩余的分组数目为1,就表示所有的城市都在一个树中,所以只需要获取当前并查集中剩余的数目,减去1,就是还需要修建的道路的数目

代码实现

public static void main(String[] args) throws Exception {
    //构建一个缓冲读取流BufferReader
    BufferedReader br =
        new BufferedReader(new InputStreamReader(Traffic_Project_Test.class.getClassLoader()
            .getResourceAsStream("traffic_project.txt")));
    //读取第一个行数据20
    int totalNumber = Integer.parseInt((br.readLine()));
    //构建一个并查集对象
    UF_Tree_Weighted uf_tree_weighted = new UF_Tree_Weighted(totalNumber);
    //读取第二行数据7
    int secondNumber = Integer.parseInt(br.readLine());
    //循环读取7条道路
    for (int i = 1; i <= secondNumber; i++) {
      //例如:0 1
      String line = br.readLine();
      String[] s = line.split(" ");
      //0
      int i1 = Integer.parseInt(s[0]);
      int i2 = Integer.parseInt(s[1]);
      //调用并查集对象的union方法让两个城市相通
      uf_tree_weighted.union(i1, i2);
    }
    //获取当前并查集剩余的分组数量并对其进行-1即可得到结果
    int lastRoads = uf_tree_weighted.count() - 1;
    System.out.println("还需要修建" + lastRoads + "条道路");
  }
Last modification:July 8, 2021
If you think my article is useful to you, please feel free to appreciate