程序员经验分享-hwhale

Java架构直通车——深入理解B+树

2023-11-08

引入：AVL树和B树

AVL树

平衡二叉搜索树是基于二分法的策略提高数据的查找速度的二叉树的数据结构；平衡二叉搜索树的数据结构组装过程有以下规则：
（1）非叶子节点只能允许最多两个子节点存在。
（2）每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)；

在这里插入图片描述

平衡树的层级结构：因为平衡二叉树查询性能和树的层级（h高度）成反比，h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如红黑树，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找。

红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

从性质5又可以推出：
性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

在这里插入图片描述
红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作，具体操作方法参考30张图带你彻底理解红黑树

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

面试准备

Java架构直通车

Java架构直通车——深入理解B+树 的相关文章

  • Java并发编程实战——彻底理解volatile

    文章目录 volatile作用 volatile实现原理 volatile的happens before关系 volatile的内存语义 volatile重排序与JMM内存屏障 volatile的使用误区 volatile的适用场景 vol

  • IT公司智力题（持续跟新中）

    请听题 用赵本山在 买车 的语气 1 有1000瓶药物 但是其中有一瓶是有毒的 小白鼠吃了一个星期以后就会死掉 请问 在一个星期内找出有毒的药物 最少需要多少只小白鼠 解答 用二进制的思路去思考 1000瓶药代表了1000种状态 那么100

  • 面试准备：操作系统常见面试题汇总

    文章目录 1 为什么要有用户态和内核态 内核态和用户态的运作方式 2 进程间通信方式介绍 3 Linux查看进程状态 cpu状态 占用端口的进程号的命令 linux top命令VIRT RES SHR DATA的含义 4 什么是Swap 5

  • 面试准备：Mybatis常见面试题汇总

    文章目录 1 和 的区别是什么 2 当实体类中的属性名和表中的字段名不一样 怎么办 3 模糊查询like语句该怎么写 4 Mybatis 一对一 一对多的xml怎么写 5 Dao 接口的工作原理是什么 Dao 接口里的方法 参数不同时 方法

  • Java架构直通车——过滤器、拦截器、AOP的区别

    文章目录 过滤器 拦截器 AOP 面向切面 三者使用场景 过滤器 过滤器拦截的是URL Spring中自定义过滤器 Filter 一般只有一个方法 返回值是void 当请求到达web容器时 会探测当前请求地址是否配置有过滤器 有则调用该过滤

  • 零拷贝的实现原理

    文章目录 引入 DMA PageCache 零拷贝 mmap sendfile SG DMA 使用零拷贝技术的项目 引入 在Java架构直通车 Kafka介绍和高性能原因一节中 介绍了Kafka的Zero Copy技术 本文将深入探究一下Z

  • Java架构直通车——点赞功能用Mysql还是Redis?

    文章目录 引入 使用Mysql实现点赞功能 使用Redis实现点赞功能 使用什么数据格式最合适 方案 引入 最近遇到一个需求 就是做联盟链做存证上 部分交易对外公开 或者是对指定人可见 之前一直在思考用Mysql怎么存合适 想来想去也没找出

  • 面试准备：Java常见面试题汇总（一）

    面试准备 Java常见面试题汇总 一 面试准备 Java常见面试题汇总 二 面试准备 Java常见面试题汇总 三 文章目录 1 面向对象的特点 特性有哪些 补充 Java的多态是编译时多态还是运行时多态 2 接口和抽象类的相同点和不同点 3

  • Java架构直通车——分布式唯一 ID生成方案

    文章目录 分布式ID的几种生成方案 UUID MySQL主键自增 数据库自增ID改进方案 雪花算法 SnowFlake 雪花算法的优化 Redis自增id Zookeeper有序节点 最近要做区块链项目 要生成很多唯一ID做业务号之类的 所

  • 面试准备：Java常见面试题汇总（二）

    面试准备 Java常见面试题汇总 一 面试准备 Java常见面试题汇总 二 面试准备 Java常见面试题汇总 三 文章目录 43 java 中的 Math round 1 5 等于多少 44 String str abc 与 String

  • 处理器对原子操作的实现

    文章目录 引入 单核 多核 引入 原子操作对于我们来说 是非常熟悉的概念 从用户角度 可以用原子操作来替换重量级的锁同步 从而提高程序性能 底层实现角度 原子操作可以用于构建各种更重量级的同步操作 比如锁或屏障之类的 对于原子操作的实现来说

  • Java架构直通车——深入理解B+树

    文章目录 引入 AVL树和B树 AVL树 红黑树 B树 B 树 数据库为什么不使用二叉树 为什么使用B 树 与B树的区别 引入 AVL树和B树 AVL树 平衡二叉搜索树是基于二分法的策略提高数据的查找速度的二叉树的数据结构 平衡二叉搜索树的

  • Java架构直通车——DispatcherServlet详解

    文章目录 引入 DispatcherServlet处理流程 DispatcherServlet与WebApplicationContext 处理流程 DispatcherServlet源码分析 init service destroy 前文

  • Java架构直通车——Java中单体应用锁的局限性&分布式锁

    文章目录 前言 单体应用锁的局限性 什么是分布式锁 目前存在的分布式的方案 前言 通过之前的并发编程的学习 对JAVA中的锁有了深刻的理解 前面内容中讲到的锁都是有JDK官方提供的锁的解决方案 也就是说这些锁只能在一个JVM进程内有效 我们

  • Java中数字的应用

    Java中数字的应用 在java中经常会遇到比较大的数 甚至超过了long型 那么该如何处理这些 大数据 呢 在java中有两个类BigInteger和BigDecimal分别表示大整数类和大浮点数类 从原则上是可以表示 天文单位 一样大的

  • Java架构直通车——过滤器和拦截器使用

    文章目录 过滤器和拦截器的区别 Filter过滤器 Interceptor拦截器 过滤器和拦截器的区别 规范不同 Filter是Servlet规范中定义的 是Servlet容器支持的 而拦截器是Spring容器内的 是Spring框架支持的

  • 测开面经总结的经常考察的知识点

    一 算法相关 1 熟悉常见的排序算法 冒泡排序 插入排序 选择排序 归并排序 堆排序 快排 希尔排序 二 计算机网络相关 1 http协议 http 超文本传输协议 是一个在客户端和服务器端之间基于请求与响应模式的 无状态的 应用层的协议

  • Java架构直通车——RabbitMQ集群架构模式

    文章目录 RabbitMQ四种架构模式 主备模式 远程模式 镜像模式 多活模式 RabbitMQ四种架构模式 主备模式 主备模式也被称为warren 兔子窝 一个主 备方案 主节点挂掉后 从节点提供服务 和ActiveMQ利用Zookeep

  • C++面试题目集合（持续跟新）

    与我前面写的C语言进阶知识点遥相呼应 这才是C 面试 网上的面试题有些太简单了 C 面试题目最多集中在对象的内存模型 记住了 如果用c c 内存都不清楚 还写个屁的程序 1 C 的虚函数是怎样实现的 C 的虚函数使用了一个虚函数表来存放了每

  • C++实现String类

    C 实现String类 还没有完成 待继续 有以下注意的点 1 赋值操作符返回的是一个MyString 而重载的 返回的是一个MyString 其中的原因参看 effective c 主要是返回引用的时候 必须返回必须在此函数之前存在的引用

随机推荐

  • 双向可控硅的四象限触发方式

    双向可控硅的四象限触发方式 双向可控硅是在普通可控硅的基础上发展而成的 它不仅能代替两只反极性并联的可控硅 而且仅需一个触发电路 是目前比较理想的交流开关器件 其英文名称TRIAC即三端双向交流开关之意 尽管从形式上可将双向可控硅看成两只普

  • SpringBoot入门到项目实战，带你快速上手springboot

    动力节点王鹤老师的SpringBoot入门系列课程 通俗易懂 基于SpringBoot2 4版本讲解 从细节入手 每个事例先讲解pom xml中的重要依赖 其次application配置文件 最后是代码实现 让你知其所以 逐步让掌握Spri

  • 适合Python 的5大练手项目，你练了么？

    往期好文推荐 0基础不用怕 从0到1轻松教你入门Python python系统学习流线图 教你一步一步学会python 但是在练手项目的选择上 还存在疑问 不知道要从哪种项目先下手 python教程入门学习 首先有两点建议 最好不要写太应用

  • ios后台运行

    iOS在升级到4 0以后就支持了多任务了 下文将详细介绍一下这个特性 1 检查设备是否支持多任务 Apple出于性能的考虑 并不是所有的iOS设备升级到iOS4以后都支持多任务 比如iPhone 3G 如果你的应用在没有多任务特性时会出问题

  • Nv21转Bitmap（高效率转化）

    转自 https blog csdn net qq1137830424 article details 81980673 版权声明 本文为博主原创文章 遵循 CC 4 0 BY SA 版权协议 转载请附上原文出处链接和本声明 本文链接 ht

  • 广义线性回归模型之0,1变量回归（logit/probit回归）—R语言实现

    1 广义线性回归 广义线性模型有三个组成部分 1 随机部分 即变量所属的指数族分布 族成员 诸如正态分布 二项分布 Poisson 分布等等 2 线性部分 即 x 3 连接函数 g R 中的广义线性模型函数glm 对指数族中某分布的默认连接

  • Redis的发布订阅模式：实现消息队列和实时数据推送的利器

    当涉及到实时数据推送和消息队列时 Redis的发布订阅模式是一种非常有用的工具 Redis是一个开源的内存数据库 被广泛用于缓存 队列和实时数据处理等方面 在本博客中 我们将重点介绍Redis的发布订阅模式 并且提供一些示例代码来帮助读者更

  • pandoc -crossref插件实现markdwon文档转word后公式编号自定义

    pandoc crossref插件实现markdwon文档转word后公式编号自定义 借助markdown撰写论文还是有一些优势的 公式可以通过vscode 提示直接快速地写出来 图片按照链接插入以后就可以自动更新图源 论文提交的时候需要转

  • Aviator 常见使用

    学习使用AviatorScript 写脚本对数据进行处理 这边写一些常见的例子 都使用表达式的方式 使用文本的话 无法传具体的参数 aviator maven最新的引用

  • 基于stm32单片机汽车胎压温度检测Proteus仿真程序

    采用stm32单片机作为主控CPU 采用BMP180传感器来测量气压和温度 采用LCD1602显示气压和温度 并且通过串口打印框也可以显示当前的气压和温度 完美的模拟出汽车胎压和温度检测相关功能 程序采用keil5编写 并且有中文注释 新手

  • [XAMPP的安装及使用教程] BUG解决

    说明 XAMPP的安装及使用教程 https blog csdn net qq 36595013 article details 80373597 转载 本文是针对原博客连接如上 安装过程中出现的bug进行解决 BUG1 前提 mysql端

  • 基于深度学习的高精度课堂人脸检测系统（PyTorch+Pyside6+YOLOv5模型）

    摘要 基于深度学习的高精度课堂人脸检测系统可用于日常生活中或野外来检测与定位课堂人脸目标 利用深度学习算法可实现图片 视频 摄像头等方式的课堂人脸目标检测识别 另外支持结果可视化与图片或视频检测结果的导出 本系统采用YOLOv5目标检测模型

  • 1084. 销售分析III（SQL）

    题目 https leetcode cn com problems sales analysis iii Table Product Column Name Type product id int product name varchar

  • demo演示是什么意思_路演（融资演示）时要注意些什么？

    路演 融资演示 究竟重不重要 如果你的企业足够优秀 那可能路演对你来说就没那么重要 甚至都不需要路演 可能就有很多投资人抢着来投你 但能达到这个水平的毕竟是少数 更多的是默默无闻的创业者 如果你的企业还没有那么优秀 或者你的产品还不够成熟

  • Python_捕获未知错误代码

    try num int input 请输入一个整数 result 8 num print result except Exception as result print 未知错误 s result

  • VScode编译调试C++环境

    首先去官网下载vscodehttps code visualstudio com 为了编译C C 要使用gcc Windows本身不支持gcc 所以有了MinGW 我用的是dev带的MinGW 也可以自己安装MinGW 或者用VS的编译器

  • VTM7.0配置并运行（windows系统）

    文章目录 一 下载安装VTM 下载方式一 下载方式二 1 解压VTM软件压缩包 2 在解压好的目录里新建 build 文件夹 二 下载安装Cmake 1 下载Cmake并解压 2 配置Cmake环境变量 三 编译 方法一 界面 1 打开 c

  • Netty案例(二)之耗时任务的处理

    文章目录 netty版本 Netty耗时任务的处理 代码案例 Handler 自定义业务线程池 Context中添加线程池 netty版本 使用的netty版本是io netty netty all 4 1 33 Final Netty耗时

  • 全网最好的免费开源ERP：Odoo库存路线规则设置应用详解

    引言 在库存管理中 供应链战略确定了产品何时应该采购或制造 交付到分销中心 并最终提供给零售渠道 在开源智造 Odoo免费开源ERP解决方案中 可以使用WMS应用中的仓库路线来配置产品的供应链策略 其中包括库内作业的拉取和推送规则 一旦一切

  • Java架构直通车——深入理解B+树

    文章目录 引入 AVL树和B树 AVL树 红黑树 B树 B 树 数据库为什么不使用二叉树 为什么使用B 树 与B树的区别 引入 AVL树和B树 AVL树 平衡二叉搜索树是基于二分法的策略提高数据的查找速度的二叉树的数据结构 平衡二叉搜索树的

热门标签