莫道桑榆晚,为霞尚满天。这篇文章主要讲述阿里二面:MySQL索引是怎么支撑千万级表的快速查找?相关的知识,希望能为你提供帮助。
前言在 mysql 官方提到,改善操作性能的最佳方法 SELECT 在查询中测试的一个或多个列上创建索引。索引条目的作用类似于指向表行的指针,从而使查询可以快速确定哪些行与WHERE子句中的条件匹配,并检索这些行的其他列值。所有MySQL数据类型都可以建立索引。
尽管可能会为查询中使用的每个可能的列创建索引,但不必要的索引会浪费空间和时间,使MySQL难以确定要使用的索引。索引还会增加插入,更新和删除的成本,因为必须更新每个索引。您必须找到适当的平衡,才能使用最佳索引集来实现快速查询。
那么,索引到底是什么?透过现象看本质:
MySQL官方对索引的定义为:索引是帮助MySQL高效获取数据的数据结构。索引的本质:索引是数据结构。
另外,阿里巴巴《java 开发手册》提出单表行数超过 500 万行或者单表容量超过 2GB,才推荐进行分库分表。对此,有阿里的黄金铁律支撑,所以,很多人设计大数据存储时,多会以此为标准,进行分表操作。
以及,阿里巴巴《Java 开发手册》补充到:如果预计三年后的数据量根本达不到这个级别,请不要在创建表时就分库分表。
【阿里二面(MySQL索引是怎么支撑千万级表的快速查找())】为了更深入理解索引的本质,这里我们先了解一下磁盘相关知识。
外存储器-磁盘计算机一般有两种存储的方式:内存储器(main memory)和外存储器(external memory)
- 内存:读写速度非常快,但是容量很小,而且造价非常贵,在不通电的情况下会数据会丢失,不能长期存储数据;
- 外存:磁盘是相对常见的外存储设备,它是以存取时间变化不大为特征的。可以直接存取任何字符组,且容量大、速度较其它外存设备更快。
文章图片
当磁盘驱动器执行读/写功能时。盘片装在一个主轴上,并绕主轴高速旋转,当磁道在读/写头(又叫磁头) 下通过时,就可以进行数据的读/写了。
一般磁盘分为固定头盘(磁头固定)和活动头盘。
固定头盘的每一个磁道上都有独立的磁头,它是固定不动的,专门负责这一磁道上数据的读/写。
活动头盘的磁头是可移动的。每一个盘面上只有一个磁头(磁头是双向的,因此正反盘面都能读写)。它可以从该面的一个磁道移动到另一个磁道,所有磁头都装在同一个动臂上,因此不同盘面上的所有磁头都是同时移动的(行动整齐划一),当盘片绕主轴旋转的时候,磁头与旋转的盘片形成一个圆柱体,各个盘面上半径相同的磁道组成了一个圆柱面,我们称为柱面。因此,柱面的个数也就是盘面上的磁道数。
磁盘的读/写原理和效率磁盘上数据必须用一个三维地址唯一标示:柱面号、盘面号、块号(磁道上的盘块)。
文章图片
读/写磁盘上某一指定数据需要下面3个步骤:
- 首先移动臂根据柱面号使磁头移动到所需要的柱面上,这一过程被称为定位或查找。
- 如上图6盘组示意图中,所有磁头都定位到了10个盘面的10条磁道上(磁头都是双向的),这时根据盘面号来确定指定盘面上的磁道。
- 盘面确定以后,盘片开始旋转,将指定块号的磁道段移动至磁头下。
访问某一具体信息,由3部分时间组成:
- 查找时间(seek time) Ts: 完成上述步骤(1)所需要的时间。这部分时间代价最高,最大可达到0.1s左右;
- 等待时间(latency time) Tl: 完成上述步骤(3)所需要的时间。由于盘片绕主轴旋转速度很快,一般为7200转/分(电脑硬盘的性能指标之一, 家用的普通硬盘的转速一般有5400rpm(笔记本)、7200rpm几种),因此一般旋转一圈大约0.0083s;
- 传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间,一般传输一个字节(byte)大概0.02us=2*10^(-8)s。
延迟时间Tr : Tr=1/(2?r)
传输时间Tt : Tt=b/(r?N)
总平均存取时间 : Ta=Ts+Tr+Tt
磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上,因此我们应该尽量将相关信息存放在同一盘块,同一磁道中,或者至少放在同一柱面或相邻柱面上,以求在读/写信息时尽量减少磁头来回移动的次数,避免过多的查找时间Ts。
所以,在大规模数据存储方面,大量数据存储在外存磁盘中,而在外存磁盘中读取/写入块(block)中某数据时,首先需要定位到磁盘中的某块,如何有效地查找磁盘中的数据,需要一种合理高效的外存数据结构。
索引的本质索引是帮助MySQL高效获取数据的排好序的数据结构
?
文章图片
索引数据结构,主要包含以下几类,我们来对比下
- 二叉树
- 平衡二叉树
- 红黑树
- Hash表
- B-Tree
缺点:会出现极端情况导致整棵树只有左子树或只有右子树。
?
文章图片
平衡二叉树(AVL Tree)定义:平衡二叉树又称AVL树,是一种特殊的二叉查找树,其左右子数都是平衡二叉树,且左右子树高度差的绝对值不超过1。
缺点:AVL树是高度平衡的,频繁的插入和删除,会引起频繁的rebalance,导致效率下降。
文章图片
红黑树定义:
- 性质1. 节点是红色或黑色。
- 性质2. 根节点是黑色。
- 性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
文章图片
Hash数据结构定义:散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 对目标值进行hash运算得到hash值和数据磁盘指针地址保存到hash表,这样就达到快速定位数据位置。
缺点:精确查找十分快速,但范围查找就碰壁了。
文章图片
BTree定义:
- 一个节点可以存储多个数据,这样可以避免黑红树的缺点,树的层数很变小;
- 叶节点具有相同的深度,叶节点的指针为空;
- 所有索引元素不重复;
- 节点中的数据索引从左到右递增排列。
文章图片
每个节点占用一个盘块的磁盘空间,一个节点上有两个升序排序的关键字和三个指向子树根节点的指针,指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例,关键字为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35。
模拟查找关键字29的过程:
- 根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】
- 比较关键字29在区间(17,35),找到磁盘块1的指针P2。
- 根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】
- 比较关键字29在区间(26,30),找到磁盘块3的指针P2。
- 根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】
- 在磁盘块8中的关键字列表中找到关键字29。
B+Tree定义:B+Tree是在B-Tree基础上的一种优化。节点里面数组数据:每个数据只存储键信息,这样不存数据可以腾出空间放更多的键信息,让树层数越小
- 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接,提高区间访问的性能
文章图片
通常在B+Tree上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种链式环结构。因此可以对B+Tree进行两种查找运算:一种是对于主键的范围查找和分页查找,另一种是从根节点开始,进行随机查找。
可能上面例子中只有22条数据记录,看不出B+Tree的优点,下面做一个推算:
InnoDB存储引擎中页的大小为16KB,一般表的主键类型为 INT(占用4个字节)或 BIGINT(占用8个字节),指针类型也一般为4或8个字节,也就是说一个页(B+Tree中的一个节点)中大概存储16KB/(8B+8B)=1K个键值。(因为是估值,为方便计算,这里的K取值为〖10〗^3)。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
实际情况中每个节点可能不能填充满,因此在数据库中,B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的,也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。
数据库中的B+Tree索引可以分为聚集索引(clustered index)和 辅助索引(secondary index)。上面的B+Tree示例图在数据库中的实现即为聚集索引,聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。
辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据,而是存储相应行数据的聚集索引键,即主键。当通过辅助索引来查询数据时,InnoDB存储引擎会遍历辅助索引找到主键,然后再通过主键在聚集索引中找到完整的行记录数据。
MySQL存储引擎 什么是存储引擎?数据库存储引擎是数据库底层软件组件,数据库管理系统使用数据引擎进行创建、查询、更新和删除数据操作。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能,使用不同的存储引擎还可以获得特定的功能。
现在许多数据库管理系统都支持多种不同的存储引擎。MySQL 的核心就是存储引擎。
- InnoDB 事务型数据库的首选引擎,支持事务安全表(ACID),支持行锁定和外键。MySQL 5.5.5 之后,InnoDB 作为默认存储引擎。
- MyISAM 是基于 ISAM 的存储引擎,并对其进行扩展,是在 Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM 拥有较高的插入、查询速度,但不支持事务。
- MEMORY 存储引擎将表中的数据存储到内存中,为查询和引用其他数据提供快速访问。
MySQL 提供了多个不同的存储引擎,包括处理事务安全表的引擎和处理非事务安全表的引擎。在 MySQL 中,不需要在整个服务器中使用同一种存储引擎,针对具体的要求,可以对每一个表使用不同的存储引擎。
MySQL 5.7 支持的存储引擎有 InnoDB、MyISAM、Memory、Merge、Archive、Federated、CSV、BLACKHOLE 等。
可以使用SHOW ENGINES语句查看系统所支持的引擎类型,结果如图所示。
文章图片
如何选择 MySQL 存储引擎不同的存储引擎都有各自的特点,以适应不同的需求,如表所示。为了做出选择,首先要考虑每一个存储引擎提供了哪些不同的功能。
文章图片
可以根据以下的原则来选择 MySQL 存储引擎:
- 如果要提供提交、回滚和恢复的事务安全(ACID 兼容)能力,并要求实现并发控制,InnoDB 是一个很好的选择。
- 如果数据表主要用来插入和查询记录,则 MyISAM 引擎提供较高的处理效率。
- 如果只是临时存放数据,数据量不大,并且不需要较高的数据安全性,可以选择将数据保存在内存的 MEMORY 引擎中,MySQL 中使用该引擎作为临时表,存放查询的中间结果。
- 如果只有 INSERT 和 SELECT 操作,可以选择Archive 引擎,Archive 存储引擎支持高并发的插入操作,但是本身并不是事务安全的。Archive 存储引擎非常适合存储归档数据,如记录日志信息可以使用 Archive 引擎。
- .frm : 存储表结构
- .MYD : 存储表数据
- .MYI :存储表索引
事务MyISAM不支持事务。
数据的存储特点MyISAM是基于非聚簇索引进行存储的。
索引实现MyISAM索引文件和数据文件是分离的(非聚集)
文章图片
其他MyISAM提供了大量的特性,包括全文索引,压缩,空间函数,延迟更新索引键等。
- 进行压缩后的表是不能进行修改的,但是压缩表可以极大减少磁盘占用空间,因此也可以减少磁盘IO,从而提供查询性能。
- 全文索引,是一种基于分词创建的索引,可以支持复杂的查询。
- 延迟更新索引键,不会将更新的索引数据立即写入到磁盘,而是会写到内存中的缓冲区中,只有在清除缓冲区时候才会将对应的索引写入磁盘,这种方式大大提升了写入性能。
- .frm : 存储表结构
- .ibd : 存储表数据和索引
事务InnoDB是典型的事务型存储引擎,并且通过一些机制和工具,支持真正的热备份。
数据的存储特点InnoDB表是基于聚簇索引建立的,聚簇索引对主键的查询有很高的性能,不过他的二级索引(非主键索引)必须包含主键列,索引其他的索引会很大。
索引实现InnoDB索引实现(聚簇)
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚簇索引-叶节点包含了完整的数据记录
- 为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?
- 为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)
文章图片
主键索引
文章图片
辅助索引
联合索引 联合索引的底层存储结构长什么样?比较相等时,先比较第一列的值,如果相等,再继续比较第二列,以此类推。
文章图片
最左前缀原理使用联合索引时,索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引(a,b,c),mysql会从最左边的列优先匹配,如果最左边的带头大哥没有使用到,在未使用覆盖索引的情况下,就只能全表扫描。 联合底层数据结构思考,mysql会优先以联合索引第一列匹配,此后才会匹配下一列,如果不指定第一列匹配的值,也就无法得知下一步查询哪个节点。 另外还有一种情况,如果遇到 > < between等这样的范围查询,那B+树中也就无法对下一列进行等值匹配了。
浅谈MVCCMySQL大多数事务型存储引擎实现的都不是简单的行锁。基于提升并发性能的考虑,他们一般都同时实现了多版本并发控制(MVCC)。
可以认为MVCC是行级锁的一个变种,它能在大多数情况下避免加锁操作,因此开销更低。无论怎样实现,它们大都实现了非阻塞的读操作,写操作也只锁定制定的行。
MVCC是通过保存数据在某一个时间点的快照来实现的,也就是说无论事务执行多久,每个事务看到的数据都是一致的。InnoDB的MVCC,是通过在每行记录后面保存两个隐藏的列来实现,这两个列一个保存了行的创建时间,一个保存了行的过期时间(或删除时间),当然,并非存储的是时间,而是系统版本号。每开启一个事务,版本号都会递增,事务开始时刻的系统版本号会作为事务的版本号。
文章图片
SELECT
- 只查询创建时间版本号小于当前事务版本号的数据行(保证事务读取的行要么在事务开始之前就存在,要么是事务本身插入的行)
- 行的删除版本号要么未定义,要么大于当前事务版本号,这样可以确保事务读取到的行,在开始事务之前未被删除
INSERT
为插入的数据保存当前系统版本号作为行版本号
DELETE
保存当前系统版本号作为删除行版本号
UPDATE
插入一行数据,并将当前系统版本号赋予行版本号;同时保存当前系统版本号到原来的行作为删除版本号。
问题总结 InnoDB一棵B+树可以存放多少行数据?这个问题的简单回答是:约2千万。为什么是这么多呢?因为这是可以算出来的,要搞清楚这个问题,我们先从InnoDB索引数据结构、数据组织方式说起。
我们都知道计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单元是块,一个块的大小是4k,而对于我们的InnoDB存储引擎也有自己的最小储存单元——页(Page),一个页的大小是16K。
下面几张图可以帮你理解最小存储单元:
文件系统中一个文件大小只有1个字节,但不得不占磁盘上4KB的空间。
文章图片
innodb的所有数据文件(后缀为ibd的文件),他的大小始终都是16384(16k)的整数倍
文章图片
磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。
文章图片
在MySQL中我们的InnoDB页的大小默认是16k,当然也可以通过参数设置:
mysql>
show variables like innodb_page_size;
+------------------+-------+
| Variable_name| Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)
数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。
如果数据库只按这样的方式存储,那么如何查找数据就成为一个问题,因为我们不知道要查找的数据存在哪个页中,也不可能把所有的页遍历一遍,那样太慢了。所以人们想了一个办法,用B+树的方式组织这些数据。如图所示:
文章图片
我们先将数据记录按主键进行排序,分别存放在不同的页中(为了便于理解我们这里一个页中只存放3条记录,实际情况可以存放很多),除了存放数据的页以外,还有存放键值+指针的页,如图中page number=3的页,该页存放键值和指向数据页的指针,这样的页由N个键值+指针组成。当然它也是排好序的。这样的数据组织形式,我们称为索引组织表。现在来看下,要查找一条数据,怎么查?
如select * from user where id=5;
这里id是主键,我们通过这棵B+树来查找,首先找到根页,你怎么知道user表的根页在哪呢?其实每张表的根页位置在表空间文件中是固定的,即page number=3的页(这点我们下文还会进一步证明),找到根页后通过二分查找法,定位到id=5的数据应该在指针P5指向的页中,那么进一步去page number=5的页中查找,同样通过二分查询法即可找到id=5的记录.
现在我们清楚了InnoDB中主键索引B+树是如何组织数据、查询数据的,总结一下:
- InnoDB存储引擎的最小存储单元是页,页可以用于存放数据也可以用于存放键值+指针,在B+树中叶子节点存放数据,非叶子节点存放键值+指针。
- 索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中,进而在去数据页中查找到需要的数据;
这里我们先假设B+树高为2,即存在一个根节点和若干个叶子节点,那么这棵B+树的存放总记录数为:根节点指针数单个叶子节点记录行数。
上文我们已经说明单个叶子节点(页)中的记录数=16K/1K=16。(这里假设一行记录的数据大小为1k,实际上现在很多互联网业务数据记录大小通常就是1K左右)。
那么现在我们需要计算出非叶子节点能存放多少指针,其实这也很好算,我们假设主键ID为bigint类型,长度为8字节,而指针大小在InnoDB源码中设置为6字节,这样一共14字节,我们一个页中能存放多少这样的单元,其实就代表有多少指针,即16384/14=1170。那么可以算出一棵高度为2的B+树,能存放1170*16=18720条这样的数据记录。
根据同样的原理我们可以算出一个高度为3的B+树可以存放:1170*1170*16=21902400条这样的记录。所以在InnoDB中B+树高度一般为1-3层,它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO,所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。
怎么得到InnoDB主键索引B+树的高度?上面我们通过推断得出B+树的高度通常是1-3,下面我们从另外一个侧面证明这个结论。在InnoDB的表空间文件中,约定page number为3的代表主键索引的根页,而在根页偏移量为64的地方存放了该B+树的page level。如果page level为1,树高为2,page level为2,则树高为3。即B+树的高度=page level+1;下面我们将从实际环境中尝试找到这个page level。
在实际操作之前,你可以通过InnoDB元数据表确认主键索引根页的page number为3,你也可以从《InnoDB存储引擎》这本书中得到确认。
SELECT
b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES a,
information_schema.INNODB_SYS_TABLES b
WHERE
a.table_id = b.table_id AND a.space <
>
0;
执行结果:
文章图片
可以看出数据库approval_db下的sys_config表、sys_config表主键索引根页的page number均为3,而其他的二级索引page number为4。
聚簇索引和非聚簇索引的区别
- 聚簇索引:将数据存储与索引放到了一块,索引结构的叶子节点保存了行数据
- 非聚簇索引:将数据与索引分开存储,索引结构的叶子节点指向了数据对应的位置
- 如果设置了主键,那么InnoDB会选择主键作为聚集索引,如果没有显式定义主键,则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引,则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。
- 如果表使用自增主键
- 如果使用非自增主键(如果身份证号或学号等)
MySQL为什么用整型自增作为索引比较好。而UUID作为索引效率比较低?聚簇索引的数据的物理存放顺序与索引顺序是一致的,即:只要索引是相邻的,那么对应的数据一定也是相邻地存放在磁盘上的。如果主键不是自增id,那么可以想象,它会干些什么,不断地调整数据的物理地址、分页,当然也有其他一些措施来减少这些操作,但却无法彻底避免。但,如果是自增的,那就简单了,它只需要一页一页地写,索引结构相对紧凑,磁盘碎片少,效率也高。
- 索引存储在磁盘,而且树的每个节点分配的空间有大小。整型占空间比较小,这样可以存放多个键值。反之然后UUID占空间比较大。
- 整型比较方便,UUID比较需要先转成ASCII在进行比较。
- 减少了出现行移动或者数据页分裂时二级索引的维护工作(当数据需要更新的时候,二级索引不需要修改,只需要修改聚簇索引,一个表只能有一个聚簇索引,其他的都是二级索引,这样只需要修改聚簇索引就可以了,不需要重新构建二级索引);
- 聚簇索引也称为主键索引,其索引树的叶子节点中存的是整行数据,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。因为索引(目录)只能按照一种方法进行排序;
- 非聚簇索引(普通索引)的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。
推荐阅读
- java企业员工出差报销预算管理系统-SSH-Mysql
- 毕业答辩过程毕业设计论文审核管理系统
- spring4.1.8扩展实战之一(自定义环境变量验证)
- ssm实验室座位管理系统的设计与实现
- 实模式与保护模式详解二(地址映射)
- 算法实验--主函数只有五行的Floyed的算法以及最短路径输出
- java_ssm幼儿园教学网站管理系统vue毕业设计
- Springboot+vue房屋租赁租房系统毕业设计
- 实模式与保护模式详解三(寻址方式)