平衡二叉树,红黑树,B树和B+树的区别及其应用场景

平衡二叉树

  • 基础数据结构
  • 左右平衡
  • 高度差大于1会自旋
  • 每个节点记录一个数据

平衡二叉树(AVL)

AVL树全称G.M. Adelson-Velsky和E.M. Landis,这是两个人的人名。

平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树, 可以保证查询效率较高。

具有以下特点:

  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
  • 并且左右两个子树都是一棵平衡二叉树。
    在这里插入图片描述
    AVL的生成演示:https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL的问题

众所周知,IO操作的效率很低,在大量数据存储中,查询时我们不能一下子将所有数据加载到内存中,只能逐节点加载(一个节点一次IO)。如果我们利用二叉树作为索引结构,那么磁盘的IO次数和索引树的高度是相关的。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。

在这里插入图片描述
为了提高查询效率,就需要 减少磁盘IO数 。为了减少磁盘IO的次数,就需要尽量降低树的高度 ,需要把原来“瘦高”的树结构变的“矮胖”,树的每层的分叉越多越好。针对同样的数据,如果我们把二叉树改成 三叉树:
在这里插入图片描述
上面的例子中,我们将二叉树变成了三叉树,降低了树的高度。如果能够在一个节点中存放更多的数据,我们还可以进一步减少节点的数量,从而进一步降低树的高度。这就是多叉树

普通树的问题

  • 左子树全部为空,从形式上看,更像一个单链表,不能发挥BST的优势。
  • 解决方案:平衡二叉树(AVL)
    在这里插入图片描述

红黑树

  • hashmap存储
  • 两次旋转达到平衡
  • 分为红黑节点

在这个棵严格的平台树上又进化为“红黑树”{是一个非严格的平衡树 左子树与右子树的高度差不能超过1},红黑树的长子树只要不超过短子树的两倍即可!

在这里插入图片描述
当再次插入7的时候,这棵树就会发生旋转

在这里插入图片描述

B+ 树和 B 树的差异:

  • B+树中非叶子节点的关键字也会同时存在在子节点中,并且是在子节点中所有关键字的最大值(或最小)。
  • B+树中非叶子节点仅用于索引,不保存数据记录,跟记录有关的信息都放在叶子节点中。而B树中, 非叶子节点既保存索引,也保存数据记录 。
  • B+树中所有关键字都在叶子节点出现,叶子节点构成一个有序链表,而且叶子节点本身按照关键字的大小从小到大顺序链接。

一个b+树中大概能存放多少条索引记录?

  • 真实环境中一个页存放的记录数量是非常大的(默认16KB),假设指针与键值忽略不计(或看做10个字节),数据占 1 kb 的空间:
  • 如果B+树只有1层,也就是只有1个用于存放用户记录的节点,最多能存放 16 条记录。
  • 如果B+树有2层,最多能存放 1600×16=25600 条记录。
  • 如果B+树有3层,最多能存放 1600×1600×16=40960000 条记录。
  • 如果存储千万级别的数据,只需要三层就够了

B+树的非叶子节点不存储用户记录,只存储目录记录,相对B树每个节点可以存储更多的记录,树的高度会更矮胖,IO次数也会更少。

使用B+树存储的索引crud执行效率如何?
c 新增

O(lognN)

N = 高度

什么是自适应哈希索引?

自适应哈希索引是Innodb引擎的一个特殊功能,当它注意到某些索引值被使用的非常频繁时,会在内存中基于B-Tree所有之上再创建一个哈希索引,这就让B-Tree索引也具有哈希索引的一些优点,比如快速哈希查找。这是一个完全自动的内部行为,用户无法控制或配置

使用命令
SHOW ENGINE INNODB STATUS \G ;

查看 INSERT BUFFER AND ADAPTIVE HASH INDEX

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520892.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

通义灵码-ai编码

https://developer.aliyun.com/topic/lingma/activities/202403?taskCode14508&recordIdb1ef3ba27250a5818b1b6ffe418af658#/?utm_contentm_fission_1 「通义灵码 体验 AI 编码,开 AI 盲盒」

使用向量检索和rerank 在RAG数据集上实验评估hit_rate和mrr

文章目录 背景简介代码实现自定义检索器向量检索实验向量检索和rerank 实验 代码开源 背景 在前面部分 大模型生成RAG评估数据集并计算hit_rate 和 mrr 介绍了使用大模型生成RAG评估数据集与评估; 在 上文 使用到了BM25 关键词检索器。接下来,想利用向…

蓝桥杯 十一届C++A组 字符排序 21分(运行超时)

思路: 1. 此题考查的冒泡排序中的交换次数,其实就是考察当前数与后面的逆序对个数问题。而为了最大利用位数,应当使每一位都不小于后面的字符,否则会造成一次逆序对的浪费(贪心,为了使总位数最少&#xff…

springBoot--阿里云短信验证

阿里云短信验证 前言阿里云短信服务免费领取100条短信服务1、开通短信服务2、申请签名3、申请模板4、通过子用户获取账号的AccessKey ID 和AccessKey Secret5、使用教程 前言 在我们平时登录中短信验证吗验证在当今是必不可少的,下面是基于阿里云开发的短信验证操作…

达梦数据库安装与实例创建:图形化方式

达梦数据库安装与实例创建:图形化方式 准备工作数据库安装与卸载安装数据库卸载数据库 实例创建与删除创建实例删除实例 准备工作 查看操作系统信息:Linux内核不能低于2.6。 [rootlocalhost ~]# cat /proc/version Linux version 4.19.90-24.4.v2101.k…

PyTorch|Dataset与DataLoader使用、构建自定义数据集

文章目录 一、Dataset与DataLoader二、自定义Dataset类(一)\_\_init\_\_函数(二)\_\_len\_\_函数(三)\_\_getitem\_\函数(四)全部代码 三、将单个样本组成minibatch(Data…

信息论基础:串联信道

串联信道 大学时候看过一期湖南卫视《快乐大本营》,那时候的主持人是何炅和李湘。节目的一个环节是邀请五名观众上台做猜谜游戏。五人带上耳机,坐在一排椅子上,两两中间隔着挡板,好像并排在一起上厕所。李湘把一部电影的名字写在…

Redis集群三种模式

一、Redis集群的三种模式 Redis有三种模式,分别是主从复制、哨兵模式、cluster 主从复制:主从复制是高可用Redis的基础,哨兵和集群都是在主从复制基础上实现高可用的。主从复制主要实现了数据的多机备份,以及对于读操作的负载均衡和简单的故障…

国家开放大学电大《钢结构》形考任务答案

电大搜题 多的用不完的题库,支持文字、图片搜题,包含国家开放大学、广东开放大学、超星等等多个平台题库,考试作业必备神器。 公众号 答案:更多答案,请关注【电大搜题】微信公众号 答案:更多答案&#x…

【windows】--- nginx 超详细安装并配置教程

目录 一、下载 nginx二、安装三、查看是否安装成功四、配置五、关闭 nginx六 负载均衡七 配置静态资源1. 根目录下的子目录(root)2.完全匹配(alias) 刷新配置(不必重启nginx)八、后端鉴权 一、下载 nginx 打开 nginx 的官网:nginx.org/ &…

K8S基于containerd做容器从harbor拉取镜

实现创建pod时,通过指定harbor仓库里的镜像来运行pod 检查:K8S是不是用containerd做容器运行时,以及containerd的版本是不是小于1.6.22 kubectl get nodes -owide1、如果containerd小于 1.6.22,需要先升级containerd 先卸载旧的…

力扣Lc28---- 557. 反转字符串中的单词 III(java版)-2024年4月06日

1.题目描述 2.知识点 1)用StringBuilder的方法 实现可变字符串结果 最后返回的时候用.toString的方法 2)在Java中使用StringBuilder的toString()方法时,它会返回StringBuilder对象当前包含的所有字符序列的字符串表示。 在我们的例子中,sb是一个Stri…

初心护蕾 珍视青春

(通讯员:赵灿飞 图:杨美、孙红浪) 为进一步加强未成年人合法权益保护工作,提高未成年人的自我安全防范意识和能力,培养未成年人正确的性观念和自我保护意识,促进健康的人际关系&#xff0c…

Debian安装宝塔教程

宝塔面板是一款非常受欢迎的服务器管理软件,它以其强大的功能、简洁的操作界面和丰富的应用生态而闻名。宝塔面板不仅能够帮助用户轻松管理服务器,还能够提供网站、数据库、FTP、备份等多种服务,是服务器管理的得力助手。 宝塔面板的特色 1.…

【Spring】之AOP详解

AOP 什么是AOP? AOP:Aspect Oriented Programming,面向切面编程。 切面指的是某一类特定问题,因此面向切面编程也可以理解为面向特定方法编程。例如,在任何一个系统中,总有一些页面不是用户可以随便访问…

设置你的第一个React应用

目录 一、React入门 1.1 你好React 1.2 创建React 1.3 应用结构 二、总结 2.1 定义组件 2.2 组件源码 三、组件详解 注意事项 3.1 组件三部曲 3.2 组件通信 —— props 3.3 对象数组迭代 —— map() 3.4 事件处理 3.5 钩子函数 —— useState() 初次学习最终效果…

Cortex-M7 内存映射模型

1 前言 如图1所示, Cortex-M7最大支持4GB的内存寻址,并对内存映射(memory map)做了初步的规定,将整个内存空间划分为了多个内存区域(region)。每个内存区域有着既定的内存类型(memory type)和内存属性(memory attribute),这两者决…

AI - ComfyUI过程图(3)

ComfyUI 比 Stable Diffusion WebUI更灵活,而且可以看到处理过程,能增加节点进行后续处理,因而更强大。 看看下面一张图的变化,一开始惨不忍睹。 使用 Ultimate SD Upscale 提升分辨率 超精后脸部有改善: 脸部比较…

递归实现指数型枚举(acwing)

题目描述: 从 1∼n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。 输入格式: 输入一个整数 n。 输出格式: 每行输出一种方案。 同一行内的数必须升序排列,相邻两个数用恰好 1 个空格隔开。 对于没有…

一周年纪念

文章目录 机缘:命运之门收获---知识之心日常---灵魂之窗成就 — 自我之光憧憬 — 未来之路 机缘:命运之门 “人生是由一连串的选择组成,而真正的成长,往往始于最具挑战性的决定。” —— 这句话恰如其分地概括了我选择跨考计算机的…