您当前的位置:首页 > 电脑百科 > 数据库 > 百科

从千万级数据查询,来聊一聊索引结构和数据库原理

时间:2020-03-18 10:34:49  来源:  作者:

在日常工作中我们不可避免地会遇到慢SQL问题,比如笔者在之前的公司时会定期收到DBA彪哥发来的Oracle AWR报告,并特别提示我某条sql近阶段执行明显很慢,可能要优化一下等。对于这样的问题通常大家的第一反应就是看看sql是不是写的不合理啊诸如:“避免使用in和not in,否则可能会导致全表扫描”“ 避免在where子句中对字段进行函数操作”等等,还有一种常见的反应就是这个表有没有加索引?绝大部分情况下,加了个索引基本上就搞定了。

既然题目是《从千万级数据查询来聊一聊索引结构和数据库原理》,首先就来构造一个千万级的表直观感受下。我们创建了一张user表,然后插入了1000万条数据,查询一下:

从千万级数据查询,来聊一聊索引结构和数据库原理

 

用了近30秒的时间,这还是单表查询,关联查询明显会更让人无法忍受。接下来,我们只是对id增加一个索引,再来验证一把:

从千万级数据查询,来聊一聊索引结构和数据库原理

 

从30s到0.02s,提升了足足1500倍。为什么加了索引之后,速度嗖地一下子就上去了呢?我们从【索引数据结构】、【MySQL原理】两个方面入手。

一、索引数据结构

我们先来看下 MySQL官方对索引的定义:

索引(Index)是帮助MySQL高效获取数据的数据结构。

这里面有2个关键词:高效查找、数据结构。对于数据库来说,查询是我们最主要的使用功能,查询速度肯定是越快越好。最基本的查找是顺序查找,更高效的查找我们很自然会想到二叉树、红黑树、Hash表、BTree等等。

1.1 二叉树

这个大家很熟悉了,他有一个很重要的特点: 左边节点的键值小于根的键值,右边节点的键值大于根的键值。比如图1,它确实能明显提高我们的搜索性能。但如果用来作为数据库的索引,明显存在很大的缺陷,但对于图2这种递增的id,存储后索引近似于变成了单边的链表,肯定是不合适的。

从千万级数据查询,来聊一聊索引结构和数据库原理

 


从千万级数据查询,来聊一聊索引结构和数据库原理

 

1.2 红黑树

也称之为平衡二叉树。在JDK1.8后,HashMap对底层的链表也优化成了红黑树(后续文章我们可以讲讲Hashmap1.8之后的调整)。平衡二叉树的结构使树的结构较好,明显提高查找运算的速度。但是缺陷也同样很明显,插入和删除运算变得复杂化,从而降低了他们的运算速度。对大数据量的支撑很不好,当数据量很大时,树的高度太高,如果查找的数据是叶子节点,依然会超级慢。

从千万级数据查询,来聊一聊索引结构和数据库原理

 

1.3 BTree

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。系统从磁盘读取数据到内存时是以磁盘块(block)为基本单位的,位于同一个磁盘块中的数据会被一次性读取到内存中。在Mysql存储引擎中有页(Page)的概念,页是其磁盘管理的最小单位。Mysql存储引擎中默认每个页的大小为16KB,查看方式:

mysql> show variables like 'innodb_page_size';
从千万级数据查询,来聊一聊索引结构和数据库原理

 

我们也可以将它修改为4K、8K、16K。系统一个磁盘块的存储空间往往没有16K,因此Mysql每次申请磁盘空间时都会将若干地址连续磁盘块来达到页的大小16KB。Mysql在把磁盘数据读入到磁盘时会以页为基本单位,在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置,这将会减少磁盘I/O次数,提高查询效率。

从千万级数据查询,来聊一聊索引结构和数据库原理

 

如上图所示,一棵B树包含有键值、存储子节点的指针信息、及除主键外的数据。相对于普通的树BTree将横向节点的容量变大,从而存储更多的索引。

1.4 B+Tree

在B-Tree的基础上大牛们又研究出了许多变种,其中最常见的是B+Tree,MySQL就普遍使用B+Tree实现其索引结构。

从千万级数据查询,来聊一聊索引结构和数据库原理

 

与B-Tree相比,B+Tree做了以下一些改进:1、非叶子节点,只存储键值信息,这样极大增加了存放索引的数据量。2、 所有叶子节点之间都有一个链指针。对于区间查询时,不需要再从根节点开始,可直接定位到数据。3、 数据记录都存放在叶子节点中。根据二叉树的特点,这个是顺序访问指针,提升了区间访问的性能。通过这样的设计,一张千万级的表最多只需要3次磁盘交互就可以找出数据。

二、Mysql部分原理说明

这一部分我们选举几个日常面试过程中或者使用过程中比较常见的问题通过问答的形式来进行讲解。

2.1、数据库引擎MyISAM和InnoDB有什么区别

  • MyISAM:
    在Mysql8之前,默认引擎是MyISAM,其目标是快速读取。
    特点:
    1、读取非常快,如果频繁插入和更新的话,因为涉及到数据全表锁,效率并不高
    2、保存了数据库行数,执行count时,不需要扫描全表;
    3、不支持数据库事务;
    4、不支持行级锁和外键;
    5、不支持故障恢复。
    6、支持全文检索FullText,压缩索引。
    建议使用场景:
    1、做很多count计算的,(如果count计算后面有where还是会全表扫描)
    2、插入和更新较少,查询比较频繁的
  • InnoDB:
    在Mysql8里,默认存储引擎改成了InnoDB。
    特点
    1、支持事务处理、ACID事务特性
    2、实现了SQL标准的四种隔离级别
    3、支持行级锁和外键约束
    4、可以利用事务日志进行数据恢复
    5、不支持FullText类型的索引,没有保存数据库行数,计算count(*)需要全局扫描
    6、支持自动增加列属性auto_increment
    7、最后也是非常重要的一点:InnerDB是为了处理大量数据时的最大性能设计,其CPU效率可能是其他基于磁盘的关系型数据库所不能匹敌的。
    建议使用场景
    1、可靠性高或者必须要求事务处理
    2、表更新和查询相当的频繁,并且表锁定的机会比较大的情况下,指定InnerDB存储引擎。

2.2 表和数据等在Mysql中是如何存储的

我们新建一个数据库mds_demo,里面有两张表:order_info,user

从千万级数据查询,来聊一聊索引结构和数据库原理

 

我们找到mysql存放数据的data目录,存在一个mds_demo的文件夹,同时我们也找到了order_info和user的文件。

从千万级数据查询,来聊一聊索引结构和数据库原理

 

为什么两张表产生了不同的文件呢?原因很简单,因为创建这两张表时使用了不同的引擎

从千万级数据查询,来聊一聊索引结构和数据库原理

 


从千万级数据查询,来聊一聊索引结构和数据库原理

 

  • MyISAM引擎在创建表的时候,会创建三个文件
    .MYD文件:存放表里的数据
    .MYI文件:存放索引数据
    .sdi文件: Serialized Dictionary Information的缩写。在Mysql5里没有sdi文件,但会有一个FRM文件,用户存放表结构信息。在MySQL8.0中重新设计了数据字典,改为sdi。
    MyISAM的索引和数据是分开的,并且索引是有压缩的,所以存储文件就会小很多,MyISAM应对错误码导致的数据恢复的速度很快。
  • InnerDB引擎在创建表的时候,只有1个文件.ibd,即存放了索引又存放了文件,参见B+Tree。所以它也被称之为聚集索引,即叶子节点包含完整的索引和数据,对应的MyISAM为非聚集索引。
    补充说明一下:存储引擎是针对表的,而不是针对数据库,同一个库的不同的表可以使用不同的引擎。

2.3 为什么InnoDB必须要有主键,并且推荐使用整型的自增主键?

通过上面的讲解这个问题其实已经很清楚了,为了满足MySQL的索引数据结构B+树的特性,必须要有索引作为主键,可以有效提高查询效率。有的童鞋可能会说我创建表的时候可以没有主键啊,这个其实和Oracle的rownum一样,如果不指定主键,InnoDB会从插入的数据中找出不重复的一列作为主键索引,如果没找到不重复的一列,InnoDB会在后台增加一列rowId做为主键索引。所以不如我们自己创建一个主键。

将索引的数据类型是设置为整型,一来占有的磁盘空间或内存空间更少,另一方面整型相对于字符串比较更快速,而字符串需要先转换为ASCII码然后再一个个进行比较的。

参见B+树的图它本质上是多路多叉树,如果主键索引不是自增的,那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡,影响数据插入的效率,如果是自增主键,只用在尾节点做增加就可以。

最后特别强调一点:不管当前是否有性能要求或者数据量多大,千万不要使用UUID作为索引。

2.4 为什么Mysql存储引擎中默认每个页的大小为16KB?

假设我们一行数据大小为1K,那么一页就能存16条数据,包含指针+数据+索引。假设一行数据大小为1K,那么一页(1个叶子节点)就能存16条数据;对于非叶子节点,假设ID为bigint类型那么长度为8B,指针大小在Innodb源码中为6B,一共就是14B,那么一页里就可以存储16K/14=1170个(主键+指针),这样一颗高度为3的B+树能存储的数据为:1170117016=2千万级别。所以我们前面1000万的数据只有0.02s。

2.5 HASH算法的使用场景

从千万级数据查询,来聊一聊索引结构和数据库原理

 

Hash算法是一种散列算法,就是计算出某个字段的hash,然后存放在对应的地址中,查找数据时只需要1次定位而不像BTree那样从根节点找到叶子节点经过多次IO操作,所以查询效率非常地高。但同样也有很多的弊端,讲一下最重要的两条。1、很明显hash只支持=、IN等查询,而不支持范围查询2、 Hash 索引在任何时候都不能避免表扫描。

所以使用时务必注意。



Tags:数据库原理   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
在日常工作中我们不可避免地会遇到慢SQL问题,比如笔者在之前的公司时会定期收到DBA彪哥发来的Oracle AWR报告,并特别提示我某条sql近阶段执行明显很慢,可能要优化一下等。对于...【详细内容】
2020-03-18  Tags: 数据库原理  点击:(72)  评论:(0)  加入收藏
▌简易百科推荐
1增1.1【插入单行】insert [into] <表名> (列名) values (列值)例:insert into Strdents (姓名,性别,出生日期) values (&#39;开心朋朋&#39;,&#39;男&#39;,&#39;1980/6/15&#3...【详细内容】
2021-12-27  快乐火车9d3    Tags:SQL   点击:(2)  评论:(0)  加入收藏
最近发现还有不少做开发的小伙伴,在写存储过程的时候,在参考已有的不同的写法时,往往很迷茫, 不知道各种写法孰优孰劣,该选用哪种写法,以及各种写法的优缺点,本文以一个简单的查询...【详细内容】
2021-12-23  linux上的码农    Tags:sql   点击:(9)  评论:(0)  加入收藏
《开源精选》是我们分享Github、Gitee等开源社区中优质项目的栏目,包括技术、学习、实用与各种有趣的内容。本期推荐的HasorDB 是一个全功能数据库访问工具,提供对象映射、丰...【详细内容】
2021-12-22  GitHub精选    Tags:HasorDB   点击:(5)  评论:(0)  加入收藏
作者丨Rafal Grzegorczyk译者丨陈骏策划丨孙淑娟【51CTO.com原创稿件】您是否还在手动对数据库执行各种脚本?您是否还在浪费时间去验证数据库脚本的正确性?您是否还需要将...【详细内容】
2021-12-22    51CTO  Tags:Liquibase   点击:(4)  评论:(0)  加入收藏
场景描述:由于生产环境的表比较复杂,字段很多。这里我们做下简化,只为说明今天要聊的问题。有两张表 tab1,tab2: tab1 数据如下: tab2 数据如下: 然后给你看下,我用来统计 name=&#3...【详细内容】
2021-12-20  Bald    Tags:SQL   点击:(7)  评论:(0)  加入收藏
前言知识无底,学海无涯,知识点虽然简单,但是比较多,所以将MySQL的基础写出来,方便自己以后查找,还有就是分享给大家。一、SQL简述1.SQL的概述Structure Query Language(结构化查...【详细内容】
2021-12-16  谣言止于独立思考    Tags:SQL基础   点击:(13)  评论:(0)  加入收藏
前言作为一名测试工程师,工作中在对测试结果进行数据比对的时候,或多或少要和数据库打交道的,要和数据库打交道,那么一些常用的 SQL 查询语法必须要掌握。最近有部分做测试小伙...【详细内容】
2021-12-14  柠檬班软件测试    Tags:SQL   点击:(15)  评论:(0)  加入收藏
话说C是面向内存的编程语言。数据要能存得进去,取得出来,且要考虑效率。不管是顺序存储还是链式存储,其寻址方式总是很重要。顺序存储是连续存储。同质结构的数组通过其索引表...【详细内容】
2021-12-08  小智雅汇    Tags:数据存储   点击:(18)  评论:(0)  加入收藏
概述DBConvert Studio 是一款强大的跨数据库迁移和同步软件,可在不同数据库格式之间转换数据库结构和数据。它将成熟、稳定、久经考验的 DBConvert 和 DBSync 核心与改进的现...【详细内容】
2021-11-17  雪竹聊运维    Tags:数据库   点击:(26)  评论:(0)  加入收藏
一、前言 大家好,我是小诚,《从0到1-全面深刻理解MySQL系列》已经来到第四章,这一章节的主要从一条SQL执行的开始,由浅入深的解析SQL语句由客户端到服务器的完整执行流程,最...【详细内容】
2021-11-09  woaker    Tags:SQL   点击:(35)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条