Mysql索引数据结构有多个选择，为什么一定要是B+树?
lipiwang 2024-11-21 17:44 6 浏览 0 评论
Mysql索引数据结构
下面列举了常见的数据结构
- 二叉树
- 红黑树
- Hash表
- B-Tree（B树）
Select * from t where t.col=5
我们在执行一条查询的Sql语句时候，在数据量比较大又不加索引的情况下，逐行查询并进行比对，每次需要从磁盘上查找，每行数据可能在磁盘不同的位置，数据比较靠后的话，一千万数据可能要比对几百万，很耗费资源。
Mysql衡量查询效率的就是磁盘IO次数，那么Mysql中应该采用什么样的数据结构存储数据呢，以及为什么要使用那个数据结构呢。
二叉树
大多数人都知道，如果加上索引之后。把数据放在二叉树里面，查询会快很多，但是还有一种特殊的情况：
把一个递增列的索引放入二叉树中，列id作为等于5查询目标，就会从col为1开始搜索，**这样要搜索几次？**二叉树插入的数据如果大于本身，会放在父节点的右下角，小的会放在父节点的左下角，因此形成了这样像链表一样的结构，其实本质还是二叉树。
需要从根节点遍历，经过5次的查找，每个节点都存储在磁盘上，每查一个节点需要跟磁盘做一次IO交互，效率相比之前没加索引也没有太大提升,这显然不是Mysql的索引结构。
红黑树
HasMap的数据结构就是红黑树，原来是数组加链表，现在优化到了数组加红黑树。
红黑树本质还是二叉树，还有一个名字又叫平衡二叉树。当一边子节点比另一边高太多的时候，会自动旋转平衡。当数据量比较大的时候比如1000万，红黑树存储的高度就可能达到几十。如果数据量越大树的高度就会越高。每查一个节点要进行一次磁盘IO交互。树的高的越高查找效率越低，很显然红黑树也不是Mysql的数据结构，早期版本Mysql有用到红黑树，现在版本没有用到红黑树。那么能不能对红黑树做点改造。
B-Tree
树的高的越高查找效率越低，那么将树高缩小，比如限制在5层，把一层存放更多元素。把一个节点的数据在磁盘同一个区域全部查出来放到内存，只做一次IO查找，就可以查到很多索引信息。B树又叫平衡多叉树。
索引值和具体data都在每个节点里，而节点的位置不固定，最好的情况查找值就在第一层。
B树的特点就是每层节点数目非常多，层数很少，目的就是为了减少磁盘IO次数，B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，由于节点内部每个 key 都带着 data 域，每次查找到具体节点还要和data进行顺序比对，如果查找某个范围内数据，又需要重新遍历。正是为了解决这个问题，B+树应运而生
B树遍历全部数据：
B+Tree
B+树节点只存储 key 的副本，真实的 key 和 data 域都在叶子节点存储，数据全部存储在叶子节，并且每一个节点之间用指针串联起来，形成链表，方便遍历，可以跨区间访问，这优点尤其突出在范围查询，不需要在一次从根节点到子节点遍历。
B+树遍历全部数据：
数据量大的情况下哪个更快，我想你应该知道了吧！
相关推荐
- linux实例之设置时区的方式有哪些
-
linux系统下的时间管理是一个复杂但精细的功能，而时区又是时间管理非常重要的一个辅助功能。时区解决了本地时间和UTC时间的差异，从而确保了linux系统下时间戳和时间的准确性和一致性。比如文件的时间...
- Linux set命令用法（linux cp命令的用法）
-
Linux中的set命令用于设置或显示系统环境变量。1.设置环境变量：-setVAR=value：设置环境变量VAR的值为value。-exportVAR：将已设置的环境变量VAR导出，使其...
- python环境怎么搭建?小白看完就会!简简单单
-
很多小伙伴安装了python不会搭建环境，看完这个你就会了Python可应用于多平台包括Linux和MacOSX。你可以通过终端窗口输入"python"命令来查看本地是否...
- Linux环境下如何设置多个交叉编译工具链?
-
常见的Linux操作系统都可以通过包管理器安装交叉编译工具链，比如Ubuntu环境下使用如下命令安装gcc交叉编译器：sudoapt-getinstallgcc-arm-linux-gnueab...
- JMeter环境变量配置技巧与注意事项
-
通过给JMeter配置环境变量，可以快捷的打开JMeter：打开终端。执行jmeter。配置环境变量的方法如下。Mac和Linux系统在~/.bashrc中加如下内容：export...
- C/C++|头文件、源文件分开写的源起及作用
-
1C/C++编译模式通常，在一个C++程序中，只包含两类文件——.cpp文件和.h文件。其中，.cpp文件被称作C++源文件，里面放的都是C++的源代码；而.h文件则被称...
- linux中内部变量，环境变量，用户变量的区别
-
unixshell的变量分类在Shell中有三种变量：内部变量,环境变量,用户变量。内部变量：系统提供，不用定义，不能修改环境变量：系统提供，不用定义，可以修改,可以利用export将用户变量转为环...
- 在Linux中输入一行命令后究竟发生了什么?
-
Linux，这个开源的操作系统巨人，以其强大的命令行界面而闻名。无论你是初学者还是经验丰富的系统管理员，理解在Linux终端输入一条命令并按下回车后发生的事情，都是掌握Linux核心的关键。从表面上看...
- Nodejs安装、配置与快速入门（node. js安装）
-
Nodejs是现代JavaScript语言产生革命性变化的一个主要框架，它使得JavaScript从一门浏览器语言成为可以在服务器端运行、开发各种各样应用的通用语言。在不同的平台下，Nodejs的安装...
- Ollama使用指南【超全版】（olaplex使用方法图解）
-
一、Ollama快速入门Ollama是一个用于在本地运行大型语言模型的工具，下面将介绍如何在不同操作系统上安装和使用Ollama。官网：https://ollama.comGithub：http...
- linux移植（linux移植lvgl）
-
1uboot移植l移植linux之前需要先移植一个bootlader代码，主要用于启动linux内核，lLinux系统包括u-boot、内核、根文件系统（rootfs）l引导程序的主要作用将...
- Linux日常小技巧参数优化（linux参数调优）
-
Linux系统参数优化可以让系统更加稳定、高效、安全，提高系统的性能和使用体验。下面列出一些常见的Linux系统参数优化示例，包括修改默认配置、网络等多方面。1.修改默认配置1.1修改默认编辑器默...
- Linux系统编程—条件变量（linux 条件变量开销）
-
条件变量是用来等待线程而不是上锁的，条件变量通常和互斥锁一起使用。条件变量之所以要和互斥锁一起使用，主要是因为互斥锁的一个明显的特点就是它只有两种状态：锁定和非锁定，而条件变量可以通过允许线程阻塞和等...
- 面试题-Linux系统优化进阶学习（linux系统的优化）
-
一.基础必备优化:1.关闭SElinux2.FirewalldCenetOS7Iptables(C6)安全组(阿里云)3.网络管理服务||NetworkManager|network...
- 嵌入式Linux开发教程:Linux Shell
-
本章重点介绍Linux的常用操作和命令。在介绍命令之前，先对Linux的Shell进行了简单介绍，然后按照大多数用户的使用习惯，对各种操作和相关命令进行了分类介绍。对相关命令的介绍都力求通俗易懂，都给...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- maven镜像 (69)
- undefined reference to (60)
- zip格式 (63)
- oracle over (62)
- date_format函数用法 (67)
- 在线代理服务器 (60)
- shell 字符串比较 (74)
- x509证书 (61)
- localhost (65)
- java.awt.headless (66)
- syn_sent (64)
- settings.xml (59)
- 弹出窗口 (56)
- applicationcontextaware (72)
- my.cnf (73)
- httpsession (62)
- pkcs7 (62)
- session cookie (63)
- java 生成uuid (58)
- could not initialize class (58)
- beanpropertyrowmapper (58)
- word空格下划线不显示 (73)
- jar文件 (60)
- jsp内置对象 (58)
- makefile编写规则 (58)