当前位置: 首页 > news >正文

对红黑树、跳表、B+树的一些理解

文章目录

      • 红黑树
        • 应用场景
      • 跳表
        • 使用场景
      • B+树
        • 使用场景

毫无疑问数据结构是复杂的,让人头大的,大学时唯一挂科的就是数据结构,上学时不用心,不晓得自己的职业生涯要一直被数据结构支配。

或多或少,面试抱佛脚时,数据结构都会背一背刷一刷,HashMap的红黑树,Redis的跳表一个个都跑不了。

当回归日常时,学习及理解数据结构真的有什么收益吗

举个例子,最近看到IO多路复用的时候,说到select,poll与epoll对比

有两个点
1.epoll通过维护一个链表来记录就绪事件,无需遍历所有文件描述符来获取所有就绪事件,而是通过事件通知机制,将就绪事件添加到链表中,epoll_wait()函数获取所有就绪事件。

int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...);
listen(s, ...)int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //将所有需要监听的socket添加到epfd中while(1) {int n = epoll_wait(...);for(接收到数据的socket){//处理}
}

2.epoll通过红黑树来维护所有文件描述符。
在这里插入图片描述

当我看到第2点时,反应是居然是你,真的有你,可算再次遇到你了,除了HashMap中,终于又和你体会到了铺面而来的重逢喜悦感,另外带着一种原来你真的挺有用的欣慰感。

红黑树、B+树以及跳表这三个数据结构,之前在我心目中,地位是一样的,需要面试的时候,对于他们我口若悬河,头头是道,而日常开发就是,对不起,我们好像不太认识。

红黑树HashMap,B+树MySQL索引,跳表Redis跳表,我几乎快要把他们画等号了,背后的原理,为什么是这样的,却从来都想不起再去深究。

随着开发的生涯越走越远,我很欣慰自己没有原地踏步,那么为什么呢?

红黑树

红黑树不算是严格的二叉平衡查找树,标准的二叉平衡查找树父子上下节点的高度最大不会超过1,为了维护这个平衡,当新增或者删除数据时,标准的平衡二叉查找树需要耗费更多的资源,不可避免需要进行多次旋转。
红黑树使得二叉查找树能保持大体的平衡,不至于退化成链表,又不至于频繁的转换操作,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。

红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。所以红黑树适用于搜索,插入,删除操作较多的情况。

应用场景

红黑树常用于存储内存中的有序数据,增删很快,内存存储不涉及 I/O 操作。

  • HashMap
  • IO多路复用-epoll
  • Linux公平调度器

跳表

1.对有序列表查询性能的优化。

2.跳表的基本思想是将有序链表分层,每个节点在不同层中拥有不同数量的前向指针。上层链表是下层链表的子集,且上层链表中的元素顺序与下层链表一致。

3.通过增加指针和添加层级的方式,跳表可以实现对数级别的查找效率。

4.实现简单

原以为除了Redis ZSet中,也不会再见到跳表了,直到看到LevelDB时,了解到其Memtable中使用的也是跳表实现。

使用场景
  • Redis zset
  • LevelDB底层数据结构

B+树

号称为文件系统而生的数据结构。

多路平衡二叉树,选用B+树最大的理由,我理解是树的高度,高度,还是tm的高度。
B+树只需要3层就能存储大约2kw的数据,定位一个数据,也就是页大的读取IO次数,最多3,4次,换成红黑树或者跳表,大概需要10倍左右;
对于文件系统、数据库的场景,需要从磁盘读取数据,IO的耗费相对于内存来说是不可接受的。

使用场景

B+ 树在处理磁盘I/O、范围查询和大数据量管理方面优势明显

  • 数据库:MySQL innodb索引,PostgreSQL索引,Oracle索引等基本主流的数据库
  • 文件系统:NTFS、ReiserFS、大名鼎鼎的HDFS等文件系统

相关文章:

对红黑树、跳表、B+树的一些理解

文章目录 红黑树应用场景 跳表使用场景 B树使用场景 毫无疑问数据结构是复杂的,让人头大的,大学时唯一挂科的就是数据结构,上学时不用心,不晓得自己的职业生涯要一直被数据结构支配。 或多或少,面试抱佛脚时&#xff0…...

C++ deque 双端队列

deque原理介绍 deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1)。 与vector比较,头插效率高,不需要搬移元素&#xf…...

Java | Leetcode Java题解之第127题单词接龙

题目&#xff1a; 题解&#xff1a; class Solution {Map<String, Integer> wordId new HashMap<String, Integer>();List<List<Integer>> edge new ArrayList<List<Integer>>();int nodeNum 0;public int ladderLength(String beginW…...

容器编排技术:现状、应用与未来

在当今的软件开发和运维中&#xff0c;容器技术已经成为一个核心组成部分。容器不仅改变了应用程序的开发、测试和部署方式&#xff0c;还推动了整个软件生命周期管理的革新。而容器编排技术作为容器管理和自动化的重要工具&#xff0c;进一步提升了容器的使用效率和灵活性。 …...

SQL158 每类视频近一个月的转发量/率

描述 用户-视频互动表tb_user_video_log iduidvideo_idstart_timeend_timeif_followif_likeif_retweetcomment_id110120012021-10-01 10:00:002021-10-01 10:00:20011NULL210220012021-10-01 10:00:002021-10-01 10:00:15001NULL310320012021-10-01 11:00:502021-10-01 11:01…...

自动化办公01 smtplib 邮件⾃动发送

目录 一、准备需要发送邮件的邮箱账号 二、发送邮箱的基本步骤 1. 登录邮箱 2. 准备数据 3. 发送邮件 三、特殊内容的发送 1. 发送附件 2. 发送图片 3. 发送超文本内容 4.邮件模板内容 SMTP&#xff08;Simple Mail Transfer Protocol&#xff09;即简单邮件传输协议…...

Flutter 中的 ScrollConfiguration 小部件:全面指南

Flutter 中的 ScrollConfiguration 小部件&#xff1a;全面指南 Flutter 是一个功能强大的 UI 框架&#xff0c;它允许开发者使用 Dart 语言来构建高性能、美观的移动、Web 和桌面应用。在 Flutter 中&#xff0c;滚动是用户界面中一个常见的交互元素。ScrollConfiguration 是…...

网络网络层

data: 2024/5/25 14:02:20 周六 limou3434 叠甲&#xff1a;以下文章主要是依靠我的实际编码学习中总结出来的经验之谈&#xff0c;求逻辑自洽&#xff0c;不能百分百保证正确&#xff0c;有错误、未定义、不合适的内容请尽情指出&#xff01; 文章目录 1.协议结构2.封装分离3.…...

【Docker】学习笔记(超万字图文整理)

前言 再此感谢黑马程序员提供的Docker课程&#xff01; 什么是Docker&#xff1f;看这一篇干货文章就够了&#xff01; UPD: 补充更新微服务集群、Docker镜像仓库部分内容 所有笔记、生活分享首发于个人博客 想要获得最佳的阅读体验&#xff08;无广告且清爽&#xff09;&#…...

el-table超过宽度强制显示滚动条

使用css强制显示&#xff1a; .el-table .el-table__body-wrapper::-webkit-scrollbar {display: block; }...

Vue3集成Phaser-飞机大战游戏(设计与源码)

文章目录 引言项目初始化游戏设计和结构游戏程序实现Vue页面嵌入PhaserPreloader 场景加载游戏场景功能实现功能类定义Boom爆炸类Bullet子弹类Enemy敌军类Player玩家类End游戏结束类 总结 更多相关内容可查看 引言 飞机大战&#xff08;也被称为射击游戏或空战游戏&#xff09…...

C51学习归纳1 --- led点亮、led闪烁、led流水灯

第一节主要是针对LED的控制学习。这个过程中我们需要掌握的&#xff1a;1、控制的实现方法&#xff0c;控制实现的方法在后续的学习中是通用的。2、如何知道谁控制谁&#xff0c;通过查找开发板原理图获取&#xff0c;原理图的阅读的能力&#xff0c;在日后也是非常常用的。 一…...

使用STM32和TB6600驱动器控制42BYGH步进电机

项目概述 1. 系统组成 STM32微控制器&#xff1a;作为主控制器&#xff0c;负责发出控制指令。TB6600驱动器&#xff1a;用于接收STM32的指令并驱动步进电机。42BYGH步进电机&#xff1a;作为执行元件&#xff0c;根据控制信号进行转动。电源&#xff1a;为STM32、TB6600和步…...

【Qt】对话框

文章目录 1 :peach:对话框介绍:peach:2 :peach:对话框的分类:peach:2.1 :apple:模态对话框:apple:2.2 :apple:非模态对话框:apple:2.3 :apple:混合属性对话框:apple: 3 :peach:Qt 内置对话框:peach:3.1 :apple:消息对话框 QMessageBox:apple: 1 &#x1f351;对话框介绍&#x…...

Python | 武理刷题

1. 为什么是非法的&#xff1f; a1a1 在Python&#xff08;以及大多数其他编程语言&#xff09;中&#xff0c;表达式 a1a1 是非法的&#xff0c;因为它试图将一个值&#xff08;a1 的结果&#xff09;赋给一个表达式&#xff08;a1 本身&#xff09;&#xff0c;而不是一个…...

如何设置让背景颜色不包括 padding 部分,顺带全面学习 background-clip 属性(可以实现文字渐变)

先解决需求 实现背景颜色不包括 padding 部分&#xff0c;直接给容器添加 css 属性&#xff1a;background-clip:content-box; 示例代码&#xff1a; .content-box-example {background-color: lightblue;padding: 20px;border: 1px solid black;background-clip: content-bo…...

Oracle 序列-SEQUENCE

文章目录 序列-SEQUENCE创建序列访问序列序列的修改和删除查询序列信息 序列-SEQUENCE 创建序列 访问序列 序列的修改和删除 DROP SEQUENCE SEQ_EKPO;查询序列信息 可以通过视图 dba/all/user_sequences 查询序列的相关信息 SELECT SEQUENCE_NAME FROM DBA_SEQUENCES WHERE …...

8岁儿童学编程基础好吗:探索早期编程教育的利与弊

8岁儿童学编程基础好吗&#xff1a;探索早期编程教育的利与弊 在数字化快速发展的今天&#xff0c;编程技能已成为一项重要的能力。许多家长开始思考&#xff0c;是否应该让8岁的孩子学习编程基础。这个问题看似简单&#xff0c;实则涉及多个层面的考量。下面&#xff0c;我们…...

vue3加axios配合element-plus实现图片等文件本地上传,并获取服务器返回的真实地址数据,前端写法

小白写法嘿嘿 开发工具和关键词 开发工具&#xff1a; vscode 关键词&#xff1a;vue3、element-plus、axios 后端 后端业务逻辑处理使用的是unicloud的云函数&#xff0c;大家可以看我上一篇文章。 思路 1、禁止element-plus的el-upload组件自动上传&#xff0c;变成手动上传…...

面试题:谈谈你对观察者和订阅发布的理解

面试题&#xff1a;谈谈你对观察者和订阅发布的理解 1. 观察者设计模式 场景引入之杂志订阅&#xff1a;小王想要购买一本尚未出版的杂志&#xff0c;他向出版社预订该杂志并提供联系方式&#xff0c;一旦该杂志出版&#xff0c;出版社就会根据小王预留的联系方式通知他可以来…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...