深入理解InnoDB索引数据结构和算法

本文涉及的产品
服务治理 MSE Sentinel/OpenSergo,Agent数量 不受限
可观测可视化 Grafana 版,10个用户账号 1个月
简介: 1. **索引定义**:索引是提升查询速度的有序数据结构,帮助数据库系统快速找到数据。2. **索引类型**:包括普通索引、唯一索引、主键索引、空间索引和全文索引,每种有特定应用场景。3. **数据结构**:InnoDB使用B+树作为索引结构,确保所有节点按顺序排列,降低查询时的磁盘I/O。4. **B+树特性**:所有数据都在叶子节点,非叶子节点仅存储索引,提供高效范围查询。5. **索引优势**:通过减少查找数据所需的磁盘I/O次数,显著提高查询性能。**总结:**InnoDB索引通过B+树结构,优化了数据访问,使得查询速度快,尤其适合大数据量的场景。

 

文本学习研究InnoDb索引数据结构和算法,从而弄明白为什么添加索引之后查询速度会有质的提升。

有人说“索引就像目录,当然快啦”,这个回答任谁都不能接受吧。至少我认为面试官肯定不满意。

抛问题:

1. 什么是索引?

2.InnoDB的数据结构是?为什么选这个数据结构?



一、索引

  1. 什么是索引?
    我经常问面试者,什么是索引?如果是你该怎么回答?先给出自己的答案,再用三个10原则提问自己
    三个10原则:
           10分钟之后再思考一下自己刚刚的回答是否满意,
           10小时之后再思考一下自己刚刚的回答是否满意,
           10天之后再思考一下自己刚刚的回答是否满意,


    停几分钟思考一下。

      定义:索引是为提升查询速度的排好序的数据结构。
           是数据结构应该好理解,
           思考:为什么是排好序的?

  2. 索引类型及应用场景
索引类型 描述 应用场景
普通索引

定义:基本的索引类型,它没有任何限制,唯一任务就是加快系统对数据的访问速度

特点:允许重复值、允许为空

创建语句:create index `索引名称` on 表名(列名 排序规则) using 使用的数据结构;

唯一索引

定义:与普通索引类似,不同的是创建唯一性索引的目的1是为了提高访问速度,2是为了避免数据出现重复

特点:数据不重复

创建语句:create union index `索引名称` on 表名(列名 排序规则) using 使用的数据结构;

为提升查询速度的同时又要保证数据的唯一性时
主键索引

定义:主键索引是一种特殊的唯一索引

特点:不允许值重复,不允许值为空

创建语句:不能用create index来创建,是用primary key 来创建

mysql中任何一张都有主键索引,如果创建表时没有指定字段为主键,mysql会自动创建一个隐藏的主键索引。
空间索引

定义:空间索引是对空间数据类型的字段建立的索引,使用 SPATIAL 关键字进行扩展

特点:NOT NULL,地理空间数据类型

创建语句:索引类型换成spatial即可


空间索引用于地理空间数据类型 GEOMETRY。在平时的工作中很少用到(我是从来没用过)。
全文索引

定义:全文索引主要用来查找文本中的关键字,只能在 CHAR、VARCHAR 或 TEXT 类型的列上创建。在 MySQL 中只有 MyISAM 存储引擎支持全文索引

特点:允许重复值和空值,只能用于创建 char,varchar,text 类型的列

创建语句:CREATE FULLTEXT INDEX `索引名称` ON 表名(列名);

用于全文检索时。

但是如果业务中明确需要全文检索,或者需要根据关键词搜索出匹配的内容,那用 ES 就比较好。

二、索引数据结构

创建索引语法:CREATE 索引类型 INDEX 索引名称 ON 表名(列名 索引排序规则)USING 数据数据结构(eg: create unique index `idx_test_col1` on test(col1 asc )using btree)

用Navicat工具可以很直观看到 using 后面除了btree 还有hash(本次不讨论hash)


直接给结论:树的高度决定IO的次数,IO次数越少,查询速度越快。

2.1  数据结构

btree是一种树结构,树有如下数据结构:

  • 普通二叉树
  • 平衡二叉树
  • b-tree
  • b+tree

树的特点:左子节点小于等于父节点,右子节点大于等于父节点。

所以左子节点一定小于等于右子节点,所以可以说所有子节点,多左到右是排好序的。

2.2 普通二叉树

假设用普通二叉树来做为索引的存储结构,假设表的主键是int的自增主键,那么随便数据的插入,根据树的特点,边子节点大于等于父节点,那么普能二叉树结构构建的索引树最终的形态会像一个键表,如下图:

image.png

image.gif

成了一个链表,根据链表的特点(链表可以看这个 ),如果有100万条数据,那么树的高度就有100万,很显示是不合适的。

2.3 平衡二叉树

平衡二叉树特点看这个,高度计算:h = log2(N+1),h约等于20,说明最坏的情况要做20次IO才能找到想要的数据。一次查询要走20次IO,如果同一时间内有100次查询就是2000次IO,搞不好服务就挂了,所以也不合适。

2.4 b-tree

结构如下图:

image.png image.gif

从图中可以看出

  • 每个节点存放的索引信息是不重复的
  • 索引信息不重复,那么索引信息和数据信息就放在一起的,所以每个节点能放的索引信息就变没多少。
    mysql默认的一叶数据大小为16kb,假如表每行的数据为1kb,那个每个节点只能放16个索引信息,假设表有100万条数据,16 * 16 * 16 * 16 * 16 = 1048576,树高度也有5

    看似树的高度大大减少了,如上图,如果是范围查询,跨数据叶查询,若查小于等小5的数据,如果先找到0000,0001,0002,要找到0004必须要回到父节点再到0004节点,对于100万条数据的树结构,很有可能要回很多个父节点。实际的IO次数是5的倍数。所以也不合适。

       由此B+ tree出现

2.5 b+tree

结构如下:

image.png

从图中可以看出

  • 叶子中包含所有非叶子节点的信息(则非叶子节点能存放更多的索引信息)
  • 叶子节点有一个箭头指向另一个叶子节点

    在mysql中使用B+Tree来作为索引的存储结构还做了修改
    叶子间的箭头是双向指向的,则对于跨数据叶的范围查询就不用返回到父点再找到另一个数据叶的数据了,相对物B- tree大大减少了IO次数。
    非叶子节点只存放索引信息,数据信息全部存放到叶子节点中。


    对于高度为3,B+tree能丰放多少呢请查看上一篇文章,这里不再计算。


    结论:非叶子节点能存放的索引信息越多,树的高度就越低,IO次数就越少,获取数据的速度就越快
相关实践学习
基于CentOS快速搭建LAMP环境
本教程介绍如何搭建LAMP环境,其中LAMP分别代表Linux、Apache、MySQL和PHP。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
3天前
|
存储 算法 物联网
R-Tree算法:空间索引的高效解决方案
【5月更文挑战第17天】R-Tree是用于多维空间索引的数据结构,常用于地理信息系统、数据库和计算机图形学。它通过分层矩形区域组织数据,支持快速查询。文章介绍了R-Tree的工作原理、应用场景,如地理信息存储和查询,以及Python的`rtree`库实现示例。此外,还讨论了R-Tree的优势(如空间效率和查询性能)与挑战(如实现复杂和内存消耗),以及优化和变种,如R* Tree和STR。R-Tree在机器学习、实时数据分析等领域有广泛应用,并与其他数据结构(如kd-trees和quad-trees)进行比较。未来趋势将聚焦于优化算法、动态适应性和分布式并行计算。
19 1
|
5天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
25 0
|
3天前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
5天前
|
缓存 监控 算法
如何调整InnoDB的LRU算法以提高效率?
【5月更文挑战第14天】如何调整InnoDB的LRU算法以提高效率?
9 2
|
5天前
|
机器学习/深度学习 算法 数据可视化
Python 数据结构和算法实用指南(四)(4)
Python 数据结构和算法实用指南(四)
10 1
|
5天前
|
机器学习/深度学习 存储 算法
Python 数据结构和算法实用指南(四)(3)
Python 数据结构和算法实用指南(四)
15 1
|
5天前
|
存储 算法 搜索推荐
Python 数据结构和算法实用指南(四)(2)
Python 数据结构和算法实用指南(四)
10 0
|
5天前
|
存储 算法 Serverless
Python 数据结构和算法实用指南(四)(1)
Python 数据结构和算法实用指南(四)
14 0
|
5天前
|
存储 关系型数据库 MySQL
MySQL引擎对决:深入解析MyISAM和InnoDB的区别
MySQL引擎对决:深入解析MyISAM和InnoDB的区别
39 0
|
3天前
|
存储 监控 关系型数据库
MySQL 参数innodb_read_io_threads
`innodb_read_io_threads` 是 MySQL 数据库中 InnoDB 存储引擎的一个配置参数,它用于指定后台线程池中用于处理读取 I/O 请求的线程数量。InnoDB 存储引擎负责管理数据库的物理存储和检索,是 MySQL 最常用的存储引擎之一。 ### 参数说明 - **名称**: `innodb_read_io_threads` - **默认值**: 4 - **范围**: 1 到 64 - **动态修改**: 不能动态修改(需要重启服务器) - **适用版本**: MySQL 5.6 及以上版本 ### 作用 `innodb_read_io_threads`