对红黑树、跳表、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树使用场景 毫无疑问数据结构是复杂的,让人头大的,大学时唯一挂科的就是数据结构,上学时不用心,不晓得自己的职业生涯要一直被数据结构支配。 或多或少,面试抱佛脚时࿰…...
C++ deque 双端队列
deque原理介绍 deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1)。 与vector比较,头插效率高,不需要搬移元素…...
Java | Leetcode Java题解之第127题单词接龙
题目: 题解: 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…...
容器编排技术:现状、应用与未来
在当今的软件开发和运维中,容器技术已经成为一个核心组成部分。容器不仅改变了应用程序的开发、测试和部署方式,还推动了整个软件生命周期管理的革新。而容器编排技术作为容器管理和自动化的重要工具,进一步提升了容器的使用效率和灵活性。 …...
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(Simple Mail Transfer Protocol)即简单邮件传输协议…...
Flutter 中的 ScrollConfiguration 小部件:全面指南
Flutter 中的 ScrollConfiguration 小部件:全面指南 Flutter 是一个功能强大的 UI 框架,它允许开发者使用 Dart 语言来构建高性能、美观的移动、Web 和桌面应用。在 Flutter 中,滚动是用户界面中一个常见的交互元素。ScrollConfiguration 是…...
网络网络层
data: 2024/5/25 14:02:20 周六 limou3434 叠甲:以下文章主要是依靠我的实际编码学习中总结出来的经验之谈,求逻辑自洽,不能百分百保证正确,有错误、未定义、不合适的内容请尽情指出! 文章目录 1.协议结构2.封装分离3.…...
【Docker】学习笔记(超万字图文整理)
前言 再此感谢黑马程序员提供的Docker课程! 什么是Docker?看这一篇干货文章就够了! UPD: 补充更新微服务集群、Docker镜像仓库部分内容 所有笔记、生活分享首发于个人博客 想要获得最佳的阅读体验(无广告且清爽)&#…...
el-table超过宽度强制显示滚动条
使用css强制显示: .el-table .el-table__body-wrapper::-webkit-scrollbar {display: block; }...
Vue3集成Phaser-飞机大战游戏(设计与源码)
文章目录 引言项目初始化游戏设计和结构游戏程序实现Vue页面嵌入PhaserPreloader 场景加载游戏场景功能实现功能类定义Boom爆炸类Bullet子弹类Enemy敌军类Player玩家类End游戏结束类 总结 更多相关内容可查看 引言 飞机大战(也被称为射击游戏或空战游戏)…...
C51学习归纳1 --- led点亮、led闪烁、led流水灯
第一节主要是针对LED的控制学习。这个过程中我们需要掌握的:1、控制的实现方法,控制实现的方法在后续的学习中是通用的。2、如何知道谁控制谁,通过查找开发板原理图获取,原理图的阅读的能力,在日后也是非常常用的。 一…...
使用STM32和TB6600驱动器控制42BYGH步进电机
项目概述 1. 系统组成 STM32微控制器:作为主控制器,负责发出控制指令。TB6600驱动器:用于接收STM32的指令并驱动步进电机。42BYGH步进电机:作为执行元件,根据控制信号进行转动。电源:为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 🍑对话框介绍&#x…...
Python | 武理刷题
1. 为什么是非法的? a1a1 在Python(以及大多数其他编程语言)中,表达式 a1a1 是非法的,因为它试图将一个值(a1 的结果)赋给一个表达式(a1 本身),而不是一个…...
如何设置让背景颜色不包括 padding 部分,顺带全面学习 background-clip 属性(可以实现文字渐变)
先解决需求 实现背景颜色不包括 padding 部分,直接给容器添加 css 属性:background-clip:content-box; 示例代码: .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岁儿童学编程基础好吗:探索早期编程教育的利与弊 在数字化快速发展的今天,编程技能已成为一项重要的能力。许多家长开始思考,是否应该让8岁的孩子学习编程基础。这个问题看似简单,实则涉及多个层面的考量。下面,我们…...
vue3加axios配合element-plus实现图片等文件本地上传,并获取服务器返回的真实地址数据,前端写法
小白写法嘿嘿 开发工具和关键词 开发工具: vscode 关键词:vue3、element-plus、axios 后端 后端业务逻辑处理使用的是unicloud的云函数,大家可以看我上一篇文章。 思路 1、禁止element-plus的el-upload组件自动上传,变成手动上传…...
面试题:谈谈你对观察者和订阅发布的理解
面试题:谈谈你对观察者和订阅发布的理解 1. 观察者设计模式 场景引入之杂志订阅:小王想要购买一本尚未出版的杂志,他向出版社预订该杂志并提供联系方式,一旦该杂志出版,出版社就会根据小王预留的联系方式通知他可以来…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
