Mysql——索引相关的数据结构

索引

引入

我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

简介

目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree(B+树)作为索引结构。B+Tree是数据库系统实现索引的首选数据结构。在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAMInnoDB两个存储引擎的索引实现方式。

索引数据结构

了解索引就需要从索引常见的数据结构开始了解学习,这是几种常见的的索引数据结构

二叉树

二叉树是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常被称之为“左子树”和“右子树”

在这里插入图片描述

二叉树示例图

左子树<父节点<=右子树

二叉树的第i层至多有有2^(i-1)个节点,

深度为K的二叉树至多总共有个2^k-1节点(定义根节点所在深度 k0=0),而总计拥有节点数符合的,称为“满二叉树”;

二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆,并应用于高效率的搜索和排序。

同时学习数据结构,这里还推荐Data Structure Visualizations进行学习,可以非常直观的看到数据结构允许的过程,一步一步的怎么走的都可以很清晰看得到。

找到其中的Binary Search Trees二叉树

可以看到二叉树不适合用作当作索引的,数据量庞大的话,或者按顺序插入 ,二叉树的层数会很大,查找效率固然也很慢了
在这里插入图片描述

红黑树(Red-Black Trees)

是一种自平衡二叉查找树,典型用途是实现关联数组。

红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在O(log n)时间内完成查找,插入和删除,这里的n是树中元素的数目。

红黑树遵行以下原则:

节点是红色或黑色。
根是黑色。
所有叶子都是黑色(叶子是NIL节点)。
每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一个具体的红黑树的图例:
在这里插入图片描述这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

要知道为什么这些性质确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

同样红黑树也不适用于MySQL的索引,数据量庞大之后,数层也会变大。

推荐阅读:

小灰红黑树

其他数据结构

由于无法装入内存,则必然依赖磁盘(或SSD)存储。而内存的读写速度是磁盘的成千上万倍(与具体实现有关),因此,核心问题是“如何减少磁盘读写次数”。

首先不考虑页表机制,假设每次读、写都直接穿透到磁盘,那么:

  • 线性结构:读/写平均O(n)次
  • 二叉搜索树(BST):读/写平均O(log2(n))次;如果树不平衡,则最差读/写O(n)次
  • 自平衡二叉搜索树(AVL):在BST的基础上加入了自平衡算法,读/写最大O(log2(n))次
  • 红黑树(RBT):另一种自平衡的查找树,读/写最大O(log2(n))次

BST、AVL、RBT很好的将读写次数从O(n)优化到O(log2(n));其中,AVL和RBT都比BST多了自平衡的功能,将读写次数降到最大O(log2(n))。

假设使用自增主键,则主键本身是有序的,树结构的读写次数能够优化到树高,树高越低读写次数越少;自平衡保证了树结构的稳定。如果想进一步优化,可以引入B树和B+树。

B树(B-Trees)

又称:多路平衡查找树。大多数存储引擎都支持B树索引。b树通常意味着所有的值都是按顺序存储的,并且每一个叶子节点到根的距离相同。B树索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取数据。下图就是一颗简单的B树。

在B树中,内部(非叶子)节点可以拥有可变数量的子节点(数量范围预先定义好)。当数据被插入或从一个节点中移除,它的子节点数量发生变化。为了维持在预先设定的数量范围内,内部节点可能会被合并或者分离。

如下图所示:
在这里插入图片描述

  • 叶节点具有相同的深度,叶节点的指针为空
  • 所有索引元素不重复
  • 节点中的数据索引从左到右递增排列
  • 无论中间节点还是叶子节点都带有卫星数据data(索引元素所指向的数据记录

只演示了插入的过程,其中可以通过delete、find执行删除和查找操作。直观的感受到B树的执行过程。

每个节点存储了多个Key和子树,子树与Key按顺序排列。

同二叉搜索树类似,每个节点存储了多个key和子树,子树与key按顺序排列。

页表的目录是扩展外存+加速磁盘读写,一个页(Page)通常4K(等于磁盘数据块block的大小,见inode与block的分析),操作系统每次以页为单位将内容从磁盘加载到内存(以摊分寻道成本),修改页后,再择期将该页写回磁盘。考虑到页表的良好性质,可以使每个节点的大小约等于一个页(使m非常大),这每次加载的一个页就能完整覆盖一个节点,以便选择下一层子树;对子树同理。对于页表来说,AVL(或RBT)相当于1个key+2个子树的B树,由于逻辑上相邻的节点,物理上通常不相邻,因此,读入一个4k页,页面内绝大部分空间都将是无效数据。

假设key、子树节点指针均占用4B,则B树节点最大m * (4 + 4) = 8m B;页面大小4KB。则m = 4 * 1024 / 8m = 512,一个512叉的B树,1000w的数据,深度最大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如AVL的深度为log(2)(10^7) = 23.25 ~= 24,相差了5倍以上。震惊!B树索引深度竟然如此!

那为什么B数这么厉害了,还有B+树的出现呢,必然是解决B树存在的问题

1、为定位行数

2、无法处理范围查询

问题1:为定位行数

数据表的记录有多个字段,仅仅定位到主键是不够的,还需要定位到数据行。有3个方案解决:

直接将key对应的数据行(可能对应多行)存储子节点中。
数据行单独存储;节点中增加一个字段,定位key对应数据行的位置。
修改key与子树的判断逻辑,使子树大于等于上一key小于下一key,最终所有访问都将落于叶子节点;叶子节点中直接存储数据行或数据行的位置。

方案1直接pass,存储数据行将减少页面中的子树个数,m减小树高增大。

方案2的节点中增加了一个字段,假设是4B的指针,则新的m = 4 * 1024 / 12m = 341.33 ~= 341,深度最大 log(341/2)(10^7) = 3.14 ~= 4。

方案3的节点m与深度不变,但时间复杂度变为稳定的O(logm(n))。

方案3可以考虑。

问题2:无法处理范围查询

实际业务中,范围查询的频率非常高,B树只能定位到一个索引位置(可能对应多行),很难处理范围查询。改动较小的是2个方案:

不改动;查询的时候先查到左界,再查到右界,然后DFS(或BFS)遍历左界、右界之间的节点。
在“问题1-方案3”的基础上,由于所有数据行都存储在叶子节点,B树的叶子节点本身也是有序的,可以增加一个指针,指向当前叶子节点按主键顺序的下一叶子节点;查询时先查到左界,再查到右界,然后从左界到有界线性遍历。

乍一看感觉方案1比方案2好——时间复杂度和常数项都一样,方案1还不需要改动。但是别忘了局部性原理,不管节点中存储的是数据行还是数据行位置,方案2的好处在于,依然可以利用页表和缓存预读下一节点的信息。而方案1则面临节点逻辑相邻、物理分离的缺点。

推荐阅读
小灰B+树

B+树

主要变动如上所述:

修改key与子树的组织逻辑,将索引访问都落到叶子节点
按顺序将叶子节点串起来(方便范围查询)

回顾上一个B树,一个m阶的B树具有如下几个特征:

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

一个m阶的B+树具有如下几个特征:

1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。

2.所有的叶子结点包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

B+树特性总结

B+树是B树的升级版,其有如下特性

非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接,提高区间访问的性能
只有叶子节点带有卫星数据data(索引元素所指向的数据记录)

在这里插入图片描述在动图中可以看出,B+树的每一个叶子节点都有一个指针指向下一个节点,把所有的叶子节点串在一起。索引数据都存储在叶子节点中。

B+树相比于B树,有什么优势呢:

1.单一节点存储更多的元素,使得查询的IO次数更少。

2.所有查询都要查找到叶子节点,查询性能稳定。

3.所有叶子节点形成有序链表,便于范围查询。

总结,B+树相比B树的优势有三:1.IO次数更少;2.查询性能稳定;3.范围查询简便。

推荐阅读:

程序员小灰-B+树

Hash索引

hash索引基于hash表实现,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中。只有精准匹配索引所有列的查询才有效。索引的检索可以一次定位,不像B-Tree索引需要从根节点出发到目标节点。虽然Hash索引很快,远高于B-tree索引,但是也有其弊端。

Hash索引仅仅能满足'=','IN','<=>'查询,也就是等值查询,不能使用范围查询。很受限
    由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系,并不能保证和Hash运算前完全一样。
由于Hash索引是通过hash表实现,其本身是没有排序的。
    由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值,而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样,所以数据库无法利用索引的数据来避免任何排序运算;
Hash索引不能利用部分索引键查询
    对于组合索引,Hash索引在计算hash值的时候是组合索引键合并后再一起计算hash值,而不是单独计算hash值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。
Hash 索引在任何时候都不能避免表扫描
    前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于不同索引键存在相同 Hash 值,所以即使取满足某个 Hash 键值的数据的记录条数,也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。
Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。
    对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。

MyISAM索引实现MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址

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

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

相关文章

缓存代理服务器

1 缓存代理 1.1 缓存代理的概述 web代理的作用 缓存网页对象&#xff0c;减少重复请求 存储一些之前被访问的或且可能将要备再次访问的静态网页资源对象&#xff0c;使用户可以直接从缓存代理服务器获取资源&#xff0c;从而减少上游原始服务器的负载压力&#xff0c;加快整…

android自定义时间选择

自定义时间选择器&#xff0c;可以更改到年月日&#xff0c;时分秒 一、自定义DatePicker public class CustomDatePicker {/*** 定义结果回调接口*/public interface ResultHandler {void handle(String time);}public enum SCROLL_TYPE {HOUR(1),MINUTE(2);SCROLL_TYPE(int …

【动态规划】【 数学】C++算法:514自由之路

作者推荐 【动态规划】458:可怜的小猪 涉及知识点 动态规划 数学 力扣514 自由之路 电子游戏“辐射4”中&#xff0c;任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘&#xff0c;并使用表盘拼写特定关键词才能开门。 给定一个字符串 ring &#x…

PyCharm安装使用教程2024

简介 PyCharm是一种PythonIDE&#xff08;Integrated Development Environment&#xff0c;集成开发环境&#xff09;&#xff0c;带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具&#xff0c;比如调试、语法高亮、项目管理、代码跳转、智能提示、自动完成、单…

【C++期末】酒店住宿信息管理系统(含easyX)

诚接计算机专业编程作业(C语言、C、Python、Java、HTML、JavaScript、Vue等)&#xff0c;如有需要请私信我&#xff0c;或者加我的企鹅号&#xff1a;1404293476 本文资源&#xff1a;https://download.csdn.net/download/weixin_47040861/88725363 目录 1.题目要求 2.实现效…

Spring Security介绍

一、Spring Security&#xff1a; 1、简介&#xff1a;Spring Security 是一个非常流行和成功的 Java 应用开发框架。Spring Security 基于 Spring 框架&#xff0c;提供了一套 Web 应用安全性的完整解决方案。一般来说&#xff0c;Web 应用的安全性包括用户认证&#xff08;A…

从吸引外资连续三年高增长看中国IT云计算科技行业的发展

​引言&#xff1a;开放合作共发展,砥砺前行迎未来 【科技明说 &#xff5c; 科技热点关注】 我今天刚注意到商务部公布的最新数据&#xff0c;2019年至2021年&#xff0c;中国吸引外资实现连续三年高增长。 2022年前11个月实际使用外资金额11560.9亿元&#xff0c;为历史同期…

【开源】基于JAVA的民宿预定管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用例设计2.2 功能设计2.2.1 租客角色2.2.2 房主角色2.2.3 系统管理员角色 三、系统展示四、核心代码4.1 查询民宿4.2 新增民宿4.3 新增民宿评价4.4 查询留言4.5 新增民宿订单 五、免责说明 一、摘要 1.1 项目介绍 基于…

C#编程-实现线程声明周期

实现线程声明周期 当System.Threading.Thread类的对象被创建的时候,线程的生命周期开始。线程的生命周期在完成任务时结束。在线程的生命周期中有各种状态。这些状态是: 未启动状态可运行状态不可运行状态死亡状态下图显示了线程的各种状态和引起线程从一个状态变为另一个状…

【Python学习】Python学习11-元组

目录 【Python学习】Python学习11-元组 前言创建语法创建语法特殊形式访问元组操作元组元组运算符元组内置函数Python列表函数&方法参考 文章所属专区 Python学习 前言 本章节主要说明Python的Python 的元组与列表类似&#xff0c;不同之处在于元组的元素不能修改。通过小…

数字档案安全与高效管理的先锋——亚信安慧AntDB数据库

档案工作在维护历史真实面貌、保障人民利益方面具有至关重要的作用。随着社会的发展&#xff0c;数字化转型成为档案管理领域的不可逆趋势。数字档案的存储和传输已经成为档案工作的重要组成部分&#xff0c;然而&#xff0c;这也伴随着一系列的挑战&#xff0c;其中安全风险是…

【云原生 • Kubernetes】认识 k8s、k8s 架构、核心概念点介绍

目录 一、Kubernetes 简介 二、Kubernetes 架构 三、Kunbernetes 有哪些核心概念&#xff1f; 1. 集群 Cluster 2. 容器 Container 3. POD 4. 副本集 ReplicaSet 5. 服务 service 6. 发布 Deployment 7. ConfigMap/Secret 8. DaemonSet 9. 核心概念总结 一、Kubern…

Leetcode18-算术三元组的数目(2367)

1、题目 给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件&#xff0c;则三元组 (i, j, k) 就是一个 算术三元组 &#xff1a; i < j < k &#xff0c; nums[j] - nums[i] diff 且 nums[k] - nums[j] diff 返回不同 算术三…

UIUC CS241 讲义:众包系统编程书

原文&#xff1a;angrave/SystemProgramming 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 欢迎来到 Angrave 的众包系统编程维基书&#xff01;这个维基是由伊利诺伊大学的学生和教师共同建立的&#xff0c;是伊利诺伊大学 CS 的 Lawrence Angrave 的众包创作实验。…

十个月,双非从零到大厂实习,我经历了什么?

个人背景 「双非大三」计科专业在读&#xff0c;某短视频「一线大厂」数据开发 22年10月份接触大数据&#xff0c;次年4月开始收割小厂实习offer&#xff0c;七月进入小厂实习&#xff0c;八月通过大厂面试 我只是万千普通人中的幸运儿&#xff0c;希望我的经历可以给一些人…

【小黑嵌入式系统第十四课】μC/OS-III程序设计基础(三)——信号量(任务同步资源同步)、事件标记组(与或多个任务)

上一课&#xff1a; 【小黑嵌入式系统第十三课】PSoC 5LP第二个实验——中断控制实验 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff1a;人工智能 文章目录 1 信号量1.1 简介1.2…

C语言之扫雷小游戏的实现【含递归展开】

文章目录 前言一、扫雷游戏代码设计思路二、设计扫雷代码1.创建菜单函数2.实现9x9扫雷3.初始化棋盘4.打印棋盘5.随机布置雷的位置6.排查雷的信息7.递归展开 三、源码1.新建一个test.c源文件2.新建一个game.c源文件3.创建一个game.h头文件 前言 扫雷游戏是1992年发行的一款大众类…

Wordpress网站开发问题解决——除了主页之外的所有页面都是“找不到页面内容”(修复记录)

一条纯经验操作 引言慌火上浇油后台查看 解决之路结尾 引言 最近 阿里云老是提醒我边缘计算机控制升级 我自己建立了一个网站&#xff0c;用的就是阿里云的万网服务器 所以 我去看看 结果跟我没什么关系 本以为就这么愉快地结束了 没想到 我建立的网站就只能打开主页 其他页…

vue3 +TS axiox接口模块添加,fast mock接口访问测试

目录 一.接口地址 二.apipost 接口测试&#xff0c;能否接通 三.安装axiox 1.下载安装依赖 2.新建src/utils/request.ts文件 2.1解释&#xff1a;后续后端真实接口需要替换baseURL&#xff0c;目前没有使用配置文件&#xff0c;后续更换 3.新建src/utils/storage.ts文件 …

九州金榜如何高质量培养孩子成长

在这个时代&#xff0c;孩子们就像温室里的花朵&#xff0c;被父母和家人宠爱着&#xff0c;享受着最优越的物质条件。 然而&#xff0c;在这样的环境中成长起来的孩子&#xff0c;却往往被很多父母称为"白眼狼"&#xff0c;对孩子的自私行为感到痛苦和失落。 1 随…