算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,高可用系列 2核4GB
简介: B+树的优势 1.单一节点存储更多元素。B+树中间节点没有卫星数据(也就是说只包含索引信息),所以每个非叶子节点可以包含更多的内容,同样大小的磁盘页可以容纳更多的节点元素。也就是说B+树会在相同数据量的情况下比B树更加“矮胖”,查询的IO次数更少。

接着来搞树!

支持云栖社区,也希望大家能支持下我的独立博客——白水东城
文章地址:
算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充

一、B+树

B+树的特征

  1. 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点
  2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接
  3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素
    如图(图片来自程序员小灰)

此处输入图片的描述

在程序员小灰的公众号里提到了一个概念——卫星数据:索引元素指向的数据记录,比如数据库中的某一行。在B+树中只有叶子节点带卫星数据,其他的中间节点只是索引,没有任何数据关联。在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。 吧

B+树的优势

  1. 单一节点存储更多元素。B+树中间节点没有卫星数据(也就是说只包含索引信息),所以每个非叶子节点可以包含更多的内容,同样大小的磁盘页可以容纳更多的节点元素。也就是说B+树会在相同数据量的情况下比B树更加“矮胖”,查询的IO次数更少。
  2. 查询效率稳定。B+树的查询必须最终找到叶子节点,而B树如果在中间节点找到匹配的即可(最好情况是只查根节点,最差是查到叶子节点),而B+树每一次都是稳定的。B-树的好处是,虽然查询性能不稳定,但平均的查询速度快一些。试想一个数据库的查询,有时候执行10毫秒,有时候执行100毫秒,肯定是不太合适的。还不如每次都执行30毫秒。
  3. 范围查询简便。B树的范围查询只能依靠繁琐的中序遍历,找到下限和上限。而B+树的范围查询很简单,只需要在叶子节点那一层的链表上做遍历就行

为什么数据库中一定要索引

二分查找,二叉树查找都依赖特定的数据结构,分别是待查找数据有序、二叉查找树,显然数据本身不能完全满足各种数据结构。
所以,数据库除了维护数据之外,还维护者满足特定查找算法的数据结构——索引,索引以某种方式引用数据,这样就可以在索引的基础上实现高级的查找等操作。目前大部分数据库系统和文件系统都采用B树或者变种的B+树来作为索引结构

为什么MySQL数据库中使用B+树

1.局部性原理与磁盘预读
由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取,而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。而这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用,程序运行期间所需要的数据通常比较集中

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。

2.数据库索引采用B+树的主要原因
根据上面的局部性原理和磁盘预读,B树中用了这个技巧:每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个结点只需一次I/O。
B树在提高了IO性能的同时并没有解决元素遍历的效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁(比如查询某段时间之内的数据)的,而B树不支持这样的操作或者说效率太低(前文已经说明效率低的原因)。

二、哈夫曼树

带权路径长度最小的树就叫最优二叉树,也就是哈夫曼树。要使带权路径长度最小,那么权值大的点就应该离根节点越近。
构造方法:先从小到大排序,然后选择最小的两棵树合并,重复这两个步骤。

哈夫曼编码

如果对一段英文转换为二进制传输,采用哈夫曼编码,让频率高的用短码,频率低的用长码,而且保证不会有某个字符的串是另一个字符的前缀(因为如果每个字符的长度不一样会出现这样的问题,比如,一个字符被11表示,另一个被110表示,出现一段11011,这样就有歧义)

哈夫曼树实现

之前数据结构课上用C写过哈夫曼树,Java的暂时不搞了,之后遇见再回来补充。

三、堆

堆是一个完全二叉树,大顶堆就是每个节点都不大于它的父节点。
插入和删除时间复杂度都是O(logn)。

堆排序

初始化一个堆,然后把无序数组的每个值都依次插入堆中,然后一直删除,把被删除的元素放到数组的最后一个有效元素之后的位置。

public class Heap {
    private int[] element;
    
    public Heap(int maxSize) {
        element = new int[maxSize];
        element[0] = 0;//存放堆中实际的个数
    }
    
    public boolean isEmpty() {
        return element[0] == 0;
    }
    public boolean isFull() {
        return element[0] == element.length - 1;
    }
    public void insert(int value) {
        if(isFull()) {
            throw new IndexOutOfBoundsException("堆已经满啦..");
        }
        if(isEmpty()) {
            element[1] = value;
        }else {
            int i = element[0] + 1;
            while(i != 1 && value > element[i / 2]) {
                element[i] = element[i / 2];
                i /= 2;
            }
            element[i] = value;
        }
        element[0] ++;
    }
    public int delete() {
        if(isEmpty()) {
            throw new IndexOutOfBoundsException("堆空啦");
        }
        int deleteElement = element[1];
        element[1] = element[element[0]];
        element[0]--;
        int value = element[1];
        int parent = 1;
        int child = 2;
        while(child <= element[0]) {
            if(child + 1 <= element[0] && element[child] < element[child + 1]) {
                child ++;
            }
            if(value >= element[child]) {
                break;
            }else {
                element[parent] = element[child];
                parent = child;
                child *= 2;
            }
        }
        element[parent] = value;
        return deleteElement;
    }
    public void printAll() {
        for(int i = 0; i < element[0]; i++) {
            System.out.print(element[i]);
            if(i != element[0]) {
                System.out.print(",");
            }
        }
        System.out.println();
    }
    public void sort() {
        int size = element[0];
        for(int i = 0; i < size; i++) {
            int deleteElement = delete();
            element[element[0] + 1] = deleteElement;
        }    
        for(int i = 1; i <= size; i++) {
            System.out.print(element[i]);
            if(i != size) {
                System.out.print(",");
            }
        }
    }
}

红黑树

红黑树的插入、删除、查找最坏时间复杂度都是O(logn)。
红黑树理解概念就OK了,目前不深入研究。
推荐一篇很好的对红黑树的概念理解文章:
漫画:什么是红黑树?

文章地址:
算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充
参考

  1. 《轻松学算法》赵烨
  2. 漫画:什么是B+树?
  3. 为什么MySQL数据库索引选择使用B+树?
  4. 数据库为什么要用B+树结构--MySQL索引结构的实现
  5. 由 B-/B+树看 MySQL索引结构
相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
70 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
65 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
1月前
|
Java 开发者
在Java的集合世界里,Set以其独特的特性脱颖而出,它通过“哈希魔法”和“红黑树防御”两大绝技
【10月更文挑战第13天】在Java的集合世界里,Set以其独特的特性脱颖而出。它通过“哈希魔法”和“红黑树防御”两大绝技,有效抵御重复元素的侵扰,确保集合的纯洁性和有序性。无论是“人海战术”还是“偷梁换柱”,Set都能从容应对,成为开发者手中不可或缺的利器。
31 6
|
1月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
107 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
22 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
1月前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
104 0
|
1月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
22 0
|
3月前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
66 2
|
3月前
|
存储 开发者 C#
WPF与邮件发送:教你如何在Windows Presentation Foundation应用中无缝集成电子邮件功能——从界面设计到代码实现,全面解析邮件发送的每一个细节密武器!
【8月更文挑战第31天】本文探讨了如何在Windows Presentation Foundation(WPF)应用中集成电子邮件发送功能,详细介绍了从创建WPF项目到设计用户界面的全过程,并通过具体示例代码展示了如何使用`System.Net.Mail`命名空间中的`SmtpClient`和`MailMessage`类来实现邮件发送逻辑。文章还强调了安全性和错误处理的重要性,提供了实用的异常捕获代码片段,旨在帮助WPF开发者更好地掌握邮件发送技术,提升应用程序的功能性与用户体验。
64 0
|
29天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。