mysql 索引(为什么选择B+ Tree?)

索引实现原理

索引:排好序数据结构
优点:降低I/O成本,CPU的资源消耗(数据持久化在磁盘中,每次查询都得与磁盘交互)
缺点:更新表效率变慢,(更新表数据,还要更新索引),占用空间
分类:主键索引,唯一索引,单值索引,组合索引

索引的数据结构

Hash表(舍弃:不适合范围查找和排序)

hash 是一维数组 + 二维链表:取模后进行存储

对于hash算法的CRUD来讲,时间复杂度为O(1)
但对于范围查询和排序来讲,时间复杂度又从最好变为O(n)

在这里插入图片描述

二叉树(舍弃:自增序列无效)

理想情况
在这里插入图片描述

mysql不使用的原因:对于自增数据,树左倾或右倾形成链表,时间复杂度变回了O(n)
在这里插入图片描述

红黑树(舍弃:树会很高)

本质就是二叉树,相比较于二叉树,他有平衡功能(当一边高时,会自动更新根节点),又称为二叉平衡树
在这里插入图片描述

mysql 不使用原因:数据量大的时候,树会更高,查找到叶子节点效率也会慢,每层就是一次IO

B Tree(舍弃:每个节点存放数据,可以优化)

特点:在每个节点,放多个索引
优点:树就不会高,但每个节点都会存data数据,会占据很大的磁盘空间
在这里插入图片描述

B+ Tree(mysql默认)

优点:
1.非叶子节点不储data,只存储索引,可以放更多的索引
2.叶子节点包含所有索引+data字段,由双向链表排成一行(更好的实现范围查找和排序)
3.叶子节点用指针连接,提高区间访问的性能

mysql 默认每个节点为16KB,
例如:若使用bigInt的主键,每个节点大概可放1170 个索引,若树高3层,则为1170*1170 *16 约为2000多万索引

在这里插入图片描述

总结:(数据存叶子节点,双向链表)

BTree 和B+Tree都是多路搜索树,区别在于叶子节点和非叶子节点的处理。
1.BTree 每个节点都储存索引+数据,B+Tree 的非叶子节点只存储索引+指向叶子节点的指针,数据存到叶子节点,这样B+Tree 的非叶子节点就可以放更多的索引,树的层级也就降低了,这样查找更快,减少了磁盘IO
2.B+Tree 的叶子节点都有指针相连接,形成双向链接表,这样在范围和排序时更快,而BTree 的叶子节点没有相连接,范围查找时还得向父节点查找。所以B+Tree 的范围查找和排序更好

数据结构训练网址

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

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

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

相关文章

DockerFile遇到的坑

CMD 命令的坑 dockerfile 中的 CMD 命令在docker run -it 不会执行 CMD 命令。 FROM golang WORKDIR / COPY . ./All-in-one CMD ["/bin/sh","-c","touch /kkk.txt && ls -la"] RUN echo alias ll"ls -la" > ~/.bashrc(不…

【LeetCode热题100】101. 对称二叉树(二叉树)

一.题目要求 给你一个二叉树的根节点 root , 检查它是否轴对称。 二.题目难度 简单 三.输入样例 示例 1: 输入:root [1,2,2,3,4,4,3] 输出:true 示例 2: 输入:root [1,2,2,null,3,null,3] 输出&a…

Zynq—AD9238数据采集DDR3缓存千兆以太网发送实验(后记)

2024.03.05: 测试了开发板网线直连电脑可以传输数据。但是通过开发板→交换机→电脑,没有数据传输。通讯采用UDP通讯,一个是无法满足后续对采集数据的傅里叶变换和傅里叶逆变换的处理。二是无法通过交换机传输数据。 2024.03.07&#xff1a…

【2024第一期CANN训练营】Ascend C算子开发进阶篇

文章目录 【2024第一期CANN训练营】Ascend C算子开发进阶篇1. 工程创建2. Kernel侧核函数实现2.1 核函数定义(add_custom.cpp)2.2 KernelAdd类实现 3. Host侧算子实现(add_custom_tiling.h ,add_custom.cpp)3.1 Tiling…

以电折水智能遥测终端机RTU应用哪些省份?

以电折水主要研究耗电量与取水量之间的关系,分析水电折算系数,进而通过计算耗电量与水电折算系数的乘积来推求取水量。 以电折水智能遥测终端机RTU通过高度集成化设计,巧妙融合了空气开关、开关电源、隔离变压器、接触器、智能电表、RTU、4G…

服务器段的连接端口和监听端口编程实现

new ServerSocket(int)是开启监听端口,并不是连接端口。真正的连接端口是随机开辟的空闲端口,当连接创建完成后,监听关口可以继续等待下一次连接请求,处于空闲等待状态。 编程实现方式 1 、主线程一直处于阻塞等待状态&#xff0c…

精通Python调试技巧:从assert开始

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 使用方法 📒📝 assert的语法📝 assert的用法示例🐾 示例1:基本用法🐾 示例2:检查变量类型🐾 示例3:检查列表长度📒 assert的注意事项⚓️ 相关链接 ⚓️📖 介绍 📖 在Python编程中,a

Java 世界破破烂烂,电音小猫缝缝补补

Java 世界破破烂烂,电音小猫缝缝补补 Java 通用代码生成器光 2.4.0 电音之王尝鲜版六正在研发,昨天发布了介绍视频,请见: https://www.bilibili.com/video/BV1yD421j7UP/ 电音之王尝鲜版六支持哑数据模式,支持枚举。…

nginx 报Too many open files

nginx 异常报 Too many open files 上周时,nginx已经报 Too many open files 当时把 配置文件调整最大连接65535了,reload 重新加载nginx后不报错了。 cat /proc/14921/limits |grep "Max open file" * soft nofile 65535 * hard nof…

界面控件DevExpress ASP.NET Scheduler - 助力快速交付个人信息管理系统(下)

DevExpress ASP. NET Scheduler组件能完全复制Microsoft Outlook Scheduler的样式和功能,具有日、周、月和时间轴视图,并包括内置的打印支持,因此用户可以在尽可能短的时间内交付全功能的个人信息管理系统。在上文中(点击这里回顾…

sentry-cli - error: Failed to load .sentryclirc file from project path

Xcode 15.2 warning sentry-cli - error: Failed to load .sentryclirc file from project path (/Users/zhuhongwei/Desktop/pandabill/.sentryclirc)推荐一下刚上线的 App 熊猫小账本,里面有用到这篇博客讲的内容 熊猫小账本 一个简洁的记账 App,用于…

聊一聊测试人如何编写一个好的测试用例!

测试用例是软件测试过程中的关键组成部分,它们用于验证软件或系统是否按照预期工作。编写一个好的测试用例对于确保软件质量、发现潜在问题以及提供清晰的反馈至关重要。 下面我们就来聊一聊,如何编写一个好的测试用例以及测试用例的执行和反馈。 一.理…

SpringCloud(22)之Sentinel实战应用

一、Sentinel核心库 sentinel主页:主页 alibaba/Sentinel Wiki GitHub 1.1 Sentinel介绍 随着微服务的流行,服务和服务之间的稳定性变得越来越重要。Sentinel 是面向分布式、多语言异构化服务架构的流量治理组件,主要以流量为切入点&…

c语言大小写字母的转换

通过ascll码表我们可以知道大写字母与小写字母相差32个数&#xff08;小写字母比大写字母大&#xff09;。因此&#xff0c;通过相加减32即可转换大小写字母。 #include <stdio.h>int main() {char ch c;char CH A;printf("%c\n", ch - 32);printf("%c…

《LeetCode热题100》笔记题解思路技巧优化_Part_4

《LeetCode热题100》笔记&题解&思路&技巧&优化_Part_4 &#x1f60d;&#x1f60d;&#x1f60d; 相知&#x1f64c;&#x1f64c;&#x1f64c; 相识&#x1f622;&#x1f622;&#x1f622; 开始刷题二叉树&#x1f7e2;1. 二叉树的中序遍历&#x1f7e2;2.…

zookeeper集群安装部署和集群异常处理

准备jdk和zookeeper安装包【官网即可下载】 zookeeper-3.5.1-alpha.tar.gz jdk1.7.0_8020200612.tar 准备三台linux虚拟机【具体以项目实际需要为准】&#xff0c;并安装jdk和zookeeper 虚拟机地址如下&#xff1a;194.1.1.86&#xff08;server.1&#xff09;、194.1.1.74…

MacOS本地使用Docker Desktop 搭建Minio容器

1. 下载docker Desktop docker官网&#xff1a;https://www.docker.com/products/docker-desktop/ 根据自己的型号进行选择&#xff0c;我的M系列芯片&#xff0c;选择的是Apple-Chip&#xff0c;记得需要看到最后噢&#xff01; 最后有坑点解决办法&#xff01; 最后有坑点解…

聚类分析 | Matlab实现基于PCA+DBO+K-means的数据聚类可视化

聚类分析 | Matlab实现基于PCADBOK-means的数据聚类可视化 目录 聚类分析 | Matlab实现基于PCADBOK-means的数据聚类可视化效果一览基本介绍程序设计参考资料 效果一览 基本介绍 PCA&#xff08;主成分分析&#xff09;、DBO&#xff08;蜣螂优化算法&#xff09;和K-means聚类…

安科瑞智慧安全用电云平台【无人化数据监控 远程控制 运维管理】

背景 在住宅火灾中&#xff0c;电气引发的居高不下&#xff0c;已查明原因的火灾中有52%系电气原因引起&#xff0c;尤其是各类家用电器、电动车、电气线路等引发的火灾越来越突出&#xff0c;仅电动自行车引发的较大火灾就有7起。这些事故暴露出电器产品生产质量、流通销售&a…

【Web】浅聊Hessian反序列化之Resin的打法——远程类加载

目录 前言 原理分析 XString&#xff1a;触发恶意类toString QName的设计理念&#xff1f; 远程恶意类加载Context&#xff1a;ContinuationContext QName&#xff1a;恶意toString利用 hash相等构造 EXP 前言 精神状态有点糟糕&#xff0c;随便学一下吧 首先明确一个…