[zz学习]MySQL索引背后的数据结构及算法原理

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介: MySQL索引背后的数据结构及算法原理MyISAM索引实现image.pngInnoDB索引实现虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

MySQL索引背后的数据结构及算法原理

MyISAM索引实现

image.png

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。
第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

图10
图10是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图11为定义在Col3上的一个辅助索引:



图11
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

B-Tree

image.png
image.png
image.png
相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
打赏
0
0
0
0
78
分享
相关文章
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
31 12
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
|
12天前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
34 3
 算法系列之数据结构-Huffman树
|
14天前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
57 22
|
14天前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
43 9
 算法系列之数据结构-二叉树
MySQL实现文档全文搜索,分词匹配多段落重排展示,知识库搜索原理分享
本文介绍了在文档管理系统中实现高效全文搜索的方案。为解决原有ES搜索引擎私有化部署复杂、运维成本高的问题,我们转而使用MySQL实现搜索功能。通过对用户输入预处理、数据库模糊匹配、结果分段与关键字标红等步骤,实现了精准且高效的搜索效果。目前方案适用于中小企业,未来将根据需求优化并可能重新引入专业搜索引擎以提升性能。
|
19天前
|
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
本文深入探讨了基于Redis实现分布式锁时遇到的细节问题及解决方案。首先,针对锁续期问题,提出了通过独立服务、获取锁进程自己续期和异步线程三种方式,并详细介绍了如何利用Lua脚本和守护线程实现自动续期。接着,解决了锁阻塞问题,引入了带超时时间的`tryLock`机制,确保在高并发场景下不会无限等待锁。最后,作为知识扩展,讲解了RedLock算法原理及其在实际业务中的局限性。文章强调,在并发量不高的场景中手写分布式锁可行,但推荐使用更成熟的Redisson框架来实现分布式锁,以保证系统的稳定性和可靠性。
38 0
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
RDS用多了,你还知道MySQL主从复制底层原理和实现方案吗?
随着数据量增长和业务扩展,单个数据库难以满足需求,需调整为集群模式以实现负载均衡和读写分离。MySQL主从复制是常见的高可用架构,通过binlog日志同步数据,确保主从数据一致性。本文详细介绍MySQL主从复制原理及配置步骤,包括一主二从集群的搭建过程,帮助读者实现稳定可靠的数据库高可用架构。
90 9
RDS用多了,你还知道MySQL主从复制底层原理和实现方案吗?
MySQL底层概述—6.索引原理
本文详细回顾了:索引原理、二叉查找树、平衡二叉树(AVL树)、红黑树、B-Tree、B+Tree、Hash索引、聚簇索引与非聚簇索引。
MySQL底层概述—6.索引原理
MySQL原理简介—12.MySQL主从同步
本文介绍了四种为MySQL搭建主从复制架构的方法:异步复制、半同步复制、GTID复制和并行复制。异步复制通过配置主库和从库实现简单的主从架构,但存在数据丢失风险;半同步复制确保日志复制到从库后再提交事务,提高了数据安全性;GTID复制简化了配置过程,增强了复制的可靠性和管理性;并行复制通过多线程技术降低主从同步延迟,保证数据一致性。此外,还讨论了如何使用工具监控主从延迟及应对策略,如强制读主库以确保即时读取最新数据。
MySQL原理简介—12.MySQL主从同步
MySQL原理简介—11.优化案例介绍
本文介绍了四个SQL性能优化案例,涵盖不同场景下的问题分析与解决方案: 1. 禁止或改写SQL避免自动半连接优化。 2. 指定索引避免按聚簇索引全表扫描大表。 3. 按聚簇索引扫描小表减少回表次数。 4. 避免产生长事务长时间执行。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等