数据库

数据库

MySQL索引凭什么能让查询效率提高这么多?

IM即时通讯柠檬^ 发表了文章 • 1 个评论 • 148 次浏览 • 2020-09-07 10:26 • 来自相关话题

背景我相信大家在数据库优化的时候都会说到索引,我也不例外,大家也基本上能对数据结构的优化回答个一二三,以及页缓存之类的都能扯上几句,但是有一次阿里P9的一个面试问我:你能从计算机层面开始说一下一个索引数据加载的流程么?(就是想让我聊IO)我当场就去世了....... ...查看全部

背景

我相信大家在数据库优化的时候都会说到索引,我也不例外,大家也基本上能对数据结构的优化回答个一二三,以及页缓存之类的都能扯上几句,但是有一次阿里P9的一个面试问我:你能从计算机层面开始说一下一个索引数据加载的流程么?(就是想让我聊IO)

我当场就去世了....因为计算机网络和操作系统的基础知识真的是我的盲区,不过后面我恶补了,废话不多说,我们就从计算机加载数据聊起,讲一下换个角度聊索引。

正文

MySQL的索引本质上是一种数据结构

让我们先来了解一下计算机的数据加载。

磁盘IO和预读:

1.png

先说一下磁盘IO,磁盘读取数据靠的是机械运动,每一次读取数据需要寻道、寻点、拷贝到内存三步操作。

寻道时间是磁臂移动到指定磁道所需要的时间,一般在5ms以下;

寻点是从磁道中找到数据存在的那个点,平均时间是半圈时间,如果是一个7200转/min的磁盘,寻点时间平均是600000/7200/2=4.17ms;

拷贝到内存的时间很快,和前面两个时间比起来可以忽略不计,所以一次IO的时间平均是在9ms左右。听起来很快,但数据库百万级别的数据过一遍就达到了9000s,显然就是灾难级别的了。

2.png

考虑到磁盘IO是非常高昂的操作,计算机操作系统做了预读的优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。

每一次IO读取的数据我们称之为一页(page),具体一页有多大数据跟操作系统有关,一般为4k或8k,也就是我们读取一页内的数据时候,实际上才发生了一次IO。

(突然想到个我刚毕业被问过的问题,在64位的操作系统中,Java中的int类型占几个字节?最大是多少?为什么?)

那我们想要优化数据库查询,就要尽量减少磁盘的IO操作,所以就出现了索引。

索引是什么?

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。

MySQL 中常用的索引在物理上分两类,B-树索引和哈希索引。

本次主要讲BTree索引。

BTree索引

BTree又叫多路平衡查找树,一颗m叉的BTree特性如下:

树中每个节点最多包含m个孩子。

除根节点与叶子节点外,每个节点至少有[ceil(m/2)]个孩子(ceil()为向上取整)。

若根节点不是叶子节点,则至少有两个孩子。

所有的叶子节点都在同一层。

每个非叶子节点由n个key与n+1个指针组成,其中[ceil(m/2)-1] <= n <= m-1 。

3.png

这是一个3叉(只是举例,真实会有很多叉)的BTree结构图,每一个方框块我们称之为一个磁盘块或者叫做一个block块,这是操作系统一次IO往内存中读的内容,一个块对应四个扇区,紫色代表的是磁盘块中的数据key,黄色代表的是数据data,蓝色代表的是指针p,指向下一个磁盘块的位置。

来模拟下查找key为29的data的过程:

1、根据根结点指针读取文件目录的根磁盘块1。【磁盘IO操作1次】

2、磁盘块1存储17,35和三个指针数据。我们发现17<29<35,因此我们找到指针p2。

3、根据p2指针,我们定位并读取磁盘块3。【磁盘IO操作2次】

4、磁盘块3存储26,30和三个指针数据。我们发现26<29<30,因此我们找到指针p2。

5、根据p2指针,我们定位并读取磁盘块8。【磁盘IO操作3次】

6、磁盘块8中存储28,29。我们找到29,获取29所对应的数据data。

由此可见,BTree索引使每次磁盘I/O取到内存的数据都发挥了作用,从而提高了查询效率。

但是有没有什么可优化的地方呢?

我们从图上可以看到,每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小,当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。

B+Tree索引

B+Tree是在B-Tree基础上的一种优化,使其更适合实现外存储索引结构。在B+Tree中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点上只存储key值信息,这样可以大大加大每个节点存储的key值数量,降低B+Tree的高度。

4.png

B+Tree相对于B-Tree有几点不同:

非叶子节点只存储键值信息, 数据记录都存放在叶子节点中, 将上一节中的B-Tree优化,由于B+Tree的非叶子节点只存储键值信息,所以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亿 条记录。(这种计算方式存在误差,而且没有计算叶子节点,如果计算叶子节点其实是深度为4了)

我们只需要进行三次的IO操作就可以从10亿条数据中找到我们想要的数据,比起最开始的百万数据9000秒不知道好了多少个华莱士了。

而且在B+Tree上通常有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种链式环结构。所以我们除了可以对B+Tree进行主键的范围查找和分页查找,还可以从根节点开始,进行随机查找。

数据库中的B+Tree索引可以分为聚集索引(clustered index)和辅助索引(secondary index)。

上面的B+Tree示例图在数据库中的实现即为聚集索引,聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据,辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据,而是存储相应行数据的聚集索引键,即主键。

当通过辅助索引来查询数据时,InnoDB存储引擎会遍历辅助索引找到主键,然后再通过主键在聚集索引中找到完整的行记录数据。

不过,虽然索引可以加快查询速度,提高 MySQL 的处理性能,但是过多地使用索引也会造成以下弊端:

创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。

除了数据表占数据空间之外,每一个索引还要占一定的物理空间。如果要建立聚簇索引,那么需要的空间就会更大。

当对表中的数据进行增加、删除和修改的时候,索引也要动态地维护,这样就降低了数据的维护速度。

注意:索引可以在一些情况下加速查询,但是在某些情况下,会降低效率。

索引只是提高效率的一个因素,因此在建立索引的时候应该遵循以下原则:

在经常需要搜索的列上建立索引,可以加快搜索的速度。

在作为主键的列上创建索引,强制该列的唯一性,并组织表中数据的排列结构。

在经常使用表连接的列上创建索引,这些列主要是一些外键,可以加快表连接的速度。

在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,所以其指定的范围是连续的。

在经常需要排序的列上创建索引,因为索引已经排序,所以查询时可以利用索引的排序,加快排序查询。

在经常使用 WHERE 子句的列上创建索引,加快条件的判断速度。

现在大家知道索引为啥能这么快了吧,其实就是一句话,通过索引的结构最大化的减少数据库的IO次数,毕竟,一次IO的时间真的是太久了。。。

总结

就面试而言很多知识其实我们可以很容易就掌握了,但是要以学习为目的,你会发现很多东西我们得深入到计算机基础上才能发现其中奥秘,很多人问我怎么记住这么多东西,其实学习本身就是一个很无奈的东西,既然我们不能不学那为啥不好好学?去学会享受呢?最近我也在恶补基础,后面我会开始更新计算机基础和网络相关的知识的。


作者:敖丙,链接:https://juejin.im/post/6869532756498448392

数据库初探(1)————关于InnoDB和MyISAM两种数据库存储引擎

IM即时通讯刘沛栋 发表了文章 • 1 个评论 • 154 次浏览 • 2020-07-14 14:58 • 来自相关话题

1.mysql中最常见的两种数据库引擎InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。MyISAM存储引擎:MyISAM存... ...查看全部

1.mysql中最常见的两种数据库引擎

InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。


MyISAM存储引擎:MyISAM存储引擎在MYSQL5.1之前的版本是默认的存储引擎,它支持大量的特性,包括全文检索,压缩等,但是它不支持行级锁和事务,而且有一个很严重的缺点就是奔溃后无法安全恢复。

  

2.在弄清楚MyISAM和InnDB存储引擎之前,我们先来搞懂什么是表级锁,什么是行级锁,什么是页级锁?


表级锁:正如他的名字一样,是锁定整张表,是Mysql目前为止锁粒度最大的锁定机制。一个用户在对表进行写操作之前,回先获得写锁,这样会阻塞其他用户的读写操作,只有没有写锁的时候,用户才会获得读锁,但是读锁之间不相互阻塞。


优点:逻辑非常简单,因为是锁定整张表,所以获取锁和释放锁的速度非常快,还可以防止死锁的发生。

缺点:因为是锁定整张表,所以锁的共享资源非常多,在并发情况下性能比较低。

使用的场景:适合以查询为主,只有按少量索引条件更新数据的应用。

支持的存储引擎:MySAM和InnoDB


行级锁:正如它的名字一样,是锁定表中的一行数据,是Mysql目前为止锁粒度最小的锁定机制,仅对指定的数据加锁,这样其他进程也会对这张表中的其他数据进行操作。


优点:因为锁的粒度非常小,所以处理高并发场景会有优势

缺点:因为锁粒度比较小,所以获取锁和释放锁的时候就会比较慢,带来的性能开销也就大了,还容易造成死锁的现象,

使用的场景:适合以大量按索引条件并发更新少量数据,同时又有高并发查询的应用。

支持的存储引擎:InnoDB


页级锁:锁的粒度位于表级锁和行级锁


3.我们现在了解了什么是表级锁和什么是行级锁,同时我们知道了两种常用的存储引擎他们分别支持哪种粒度的锁,即MyISAM支持表级锁,InnoDB支持行级锁和页级锁,那么他们两种存储引擎具体有什么区别呢?


(1)首先我们说最重要的一点,就是MyISAM不支持事务,但是InnoDB支持事务。在使用InnoDB的时候,会默认将每一条sql语句都封装成事务,自动提交,这样会影响速度,所以最好把多条语句放在begin和commit之间,组成一个事务。

(2)InnoDB支持外键,但是MyISAM不支持外键。一个具有外键的InnoDB的表不能转化成MyISAM表。

(3)InnoDB不支持全文检索,但是MyISAM支持全文检索。在涉及全文检索的项目中MyISAM速度更快。PS:MyIsam在5.7以后也支持全文检索。

(4)InnoDB支持表级锁和行级锁,MyISAM支持表级锁。

(5)InnoDB必须有主键(没有的话会自动生成),MyISAM可以没有主键。

(6)InnoDB的索引是聚集索引,使用的是B+树的数据结构(后面会详细分析B+树和B树的数据结构)。聚集索引的意思是数据文件和主键索引(后面会详细讲)是捆绑在一起的,我们一般推荐使用主键索引,因为一次性查到数据文件这样的效率高,不推荐使用辅助索引(辅助索引中包含主键列),因为这样会先找到主键,再通过主键找到数据文件,就会进行两次查询。总的来说,就是主键索引存放的是数据文件,辅助索引存放的是主键的值。

MyISAM的索引是非聚集索引,使用的是B+树的数据结构。非聚集索引的意思是数据文件和索引是分开的(注意这里是索引,而不是主键索引,因为我们上面说过MyISAM可以没有主键索引),索引中存放的是数据文件的地址。

(7)表的具体行数,在MyISAM存储引擎中,保存有表的总行数,通过select count(*) from table直接取出。在InnoDB存储引擎中,没有保存表的行数,通过select count(*) from table会遍历整个表,性能消耗极大。在这里注意的一点就是,在加入where条件后,两种存储引擎的效率相同。


4.我们了解了两种存储引擎的区别,那么我们如何选择使用哪种存储引擎呢?

(1)看是否需要支持事务,如果不需要,则使用MyISAM,如果需要的话,就使用InnoDB。

(2)如果对数据库只有读的操作,建议使用MyISAM,如果对数据库的操作既有读又有写,那么建议使用InnoDB。


5.从上述的几个问题中我们大概了解到什么是MyISAM和InnoDB,那么面试中我们应该如何更好的向面试官谈呢?

我们应该先从这两种数据库存储引擎的优点开始分析,再谈到索引,然后谈到他们的应用场景:

InnoDB引擎,它提供了对数据库事务ACID的支持,行级锁和表级锁的支持,支持外键。

采用的是聚集索引,聚集索引的意思是叶节点data域保存了完整的数据记录,索引的key就是数据表的主键,因此InnoDB表数据文件本身就是主索引。除了主索引还有辅助索引,InnoDB的辅助索引的data域是主键。聚集索引推荐使用主键索引,因为这样查询速度比较快。

MYSQL运行的时候,InnoDB会在内存中创建缓冲池,用户缓冲数据以及索引,但是它的启动比较慢,并且没有保存表的行数。所以,这类引擎 当你需要数据库事务支持的时候,该引擎就是首选,由于锁的粒度比较小,写操作的时候不会锁定整张表,所以支持高并发的场景。事实上,InnoDB存储引擎现已是最主流的存储引擎。



MyISAM引擎,它不提供对数据库事务ACID的支持,它支持表级锁,不支持外键,所以它在写的时候,会锁定整张表,对表处理的性能就会变慢。

采用的是非聚集索引,非聚集索引指叶节点的data域保存的是数据文件的地址,而辅助索引和主索引没有什么区别,唯一的区别就是主索引的key是唯一的,辅助索引的key可以不唯一。

好处就是MyIsam保存了表的行数,在执行select count(*) from table 的时候,可以直接读取已经保存的值而不会遍历整张表,InnoDB存储引擎没有这一功能。

当数据库的读的操作多于写操作的时候,并且不要求事务的支持的时候,优先使用MyISAM存储引擎。


6.在上述问题中,我们频繁提到了索引,索引对于构建数据库有着至关重要的地位,那么什么是索引呢?

我们首先要清楚一点,如果我们合理的设计数据库并且合理的利用索引,会大大提升数据库检索的性能,但是如果我们滥用数据库的索引,反而会影响数据库的性能。

第一点是数据库的索引是利用空间换时间的策略,将数据的引用按照合适的数据结构进行存储就是我们所说的索引。第二点我们数据库的索引通常情况下使用的是B+树的数据结构,因为B+树非常适合文件系统查找。


7.上面的问题我们了解到了什么是索引,那么MyISAM和InnoDB的索引结构到底长什么样呢?我们分成主键索引和辅助索引来讨论。


我们来引用网络上的图来说明这个问题:

首先说MyISAM索引实现:

1.主键索引:

679616-20180115165534912-4452270.png

MyISAM为B+树的数据结构作为索引,从上图我们可以看出,叶子节点data域存储的是数据文件的地址,Col1为主键。

2.辅助索引:

2.png

在MyISAM存储引擎中,我们看到辅助索引和主键索引没有什么区别,只是主键索引要求key是唯一的,辅助索引的key可以是不唯一的,上图在col2上建立一个辅助索引。

我们可以看出,MyISAM存储引擎的索引策略:B+树叶子节点data域保存的是数据文件的地址,因此,MyISAM中索引检索的算法首先按照B+树搜索算法搜索索引,如果指定的key存在的话,就取出其data域的值,这个值是数据文件的地址,再通过打他域的地址,找到数据文件,因此,叫它非聚集索引,主要目的就是和聚集索引做一个区分。


我们再来讨论下InnoDB索引实现:

1.主键索引:

3.png

同样是B+树,但是实现方式确是不同的,InnoDB表数据文件本身就是一个索引结构,它的叶子节点data域保存了完整的数据记录,因为InnoDB的数据文件本身就是按照主键聚集,所以InnoDB表必须有主键,如果没有显示显示,则我们的数据库会自动的选择一个具有唯一标识列来作为主键,如果还是没有,则数据库自动创建一个主键列。

2.辅助索引:

4.png

上图中可以看出,InnoDB存储引擎所有辅助索引都是以主键作为Data域。

但是我们在检索的时候,InnoDB存储引擎推荐使用主键索引,因为这种聚聚索引的方式(主键上的都是自增的,所以范围查找的时候会更加快速)使得按照主键索引非常的高效。但是辅助索引需要检索两遍索引,首先辅助索引先找到主键索引,再通过主键索引找到数据文件。


不同存储引擎的索引实现对于我们正确使用和优化索引都非常有帮助,例如我们知道了InnoDB的索引实现以后,我们就知道了为什么不能用过长字段的值作为主键,因为辅助索引中包含主键索引,主键索引过长,就会导致辅助索引也过长。

还有一个例子就是使用非单调的字段作为主键在InnoDB中是不好的,因为InooDB数据文件本身就是一颗B+树,非单调的主键会造成数据文件一位要维持B+树的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键是一个很好的选择。


8.上面我们说了那两种存储引擎,我们直到B+树的数据结构用在索引中是最好的,我们在讨论B+树的时候,经常会讨论B树,那么B树和B+树有什么区别呢?

(1)B树的关键字分布在整棵树上,B+树的关键字分布在叶子节点上,且叶子节点的顺序本身就是自小到大有序的(链表形式)。

(2)查找过程虽然类似,但是B树的搜索有可能在非叶子节点上完成,B+树的搜索只能在叶子节点上完成,从根节点一直到叶子节点。

(3)B树在插入,删除的时候要进行不断的分类以及合并,会破坏B树的性质。

(4)B+树的非叶子节点相当于叶子节点的索引,叶子节点相当于存储系统的数据库。

(5)B+树比B树更适合数据库的索引,B树更适合文件系统的索引(如MangoDB)。


5.png

6.png

注:B+树有所演变,B+树在非叶子节点上添加了顺序访问指针,就在在每一个叶子节点上添加了指向下一个叶子节点的指针,提高了区间访问的性能。


9.我们了解了B+树和B树的优点的缺点后,那么为什么Mysql的存储引擎要使用B+树而不是使用B数呢?(面试常问)

从查询性能来看,因为B+树所有的数据文件都在叶子节点上,并且所有的叶子节点都是用指针互相连接。这时候,我们考虑一个业务场景,如果我们要从数据库中select多条数据,比如最后10条。如果我们使用B数,因为B树的非叶子节点也保存着数据文件,如果要查询,肯定有中序查找,这时候,我们势必要跨层查找。如果是B+树,因为B+树所有的数据都保存在叶子节点中,不用跨层,且有链表的形式,所以若能很快的找到首部元素,就能够很快的找到需要查找到的数据。


从操作系统层面来考虑,因为B树不管是叶子节点还是非叶子节点都要保存数据,这样就会使非叶子节点保存的指针数量变少,指针数量少的情况要保存大量的数据,就会使树的高度增加,一旦树的高度增加,就会使磁盘I/O的次数增加,查询性能就会变高。


10.hash存储索引的时间复杂度是O(1),B+树的时间复杂度是O(nlogn),那么为什么数据库的索引是B+树呢?(面试题常问)

这还是和我们的业务场景有关,如果我们查询单条数据,那么的确是hash索引的效率更高,但是我们在数据库中出现单条查询的情况少之又少,一般都是多条查询,使用B+树主键索引有序,且有链表的数据结构,就能很快查找出多条数据。

还有三个原因:

(1)索引一般保存在我们的硬盘中,可能不能一次性全部加载进内存中,而B+树的设计支持数据分批加载。

(2)使用B+树因为树的高度比较低,磁盘I/O的次数少,查询性能就会提高。

(3)再一个就是存在模糊查询的情况,哈希表是不支持模糊查询的,只能遍历整张表,而B+树可以采用最左前缀的原则进行查询找到相应的数据。


11.我们知道数据库的存储引擎一般采用的是B+树数据结构的索引,那么哪些是使用B树的数据结构呢?

MangoDB


12.为什么MangoDB采用的是B树的数据结构作索引的结构?

我们知道,索引的结构一般是红黑树,B树或者红黑树,因为这些树是多路树,使用多路数,可以降低树的高度。

文件系统(MangoDB)和数据库的索引都是存放在硬盘中,并且数据量很大的情况,就不能一次性加载进内存,如果是红黑树,就不能保证一次性都加载进内存,所以使用B树的结构,我们每次加载B树的一个节点,然后一步一步加载。

假设内存中每次只能加载两个字节的数据,那么长的有序数组无法一次性全部加载,要是我们设计成一个3路的B 树,那么一个节点最多有两个数,查找的时候,每次加载进一个节点就可以了。

如果是在内存中,红黑树比B树的效率更高,如果实在硬盘中保存,那么B树更优。


13.我们上面提到了红黑树,那么到底什么是红黑树呢?

我们知道,二叉排序树就是节点的左孩子的值小于该节点的值,该节点的右孩子的值大于该节点的值。那么在一些极端情况下,会出现链表的情况。这时候,我们就引入了平衡而二叉树的概念,平衡二叉树的意思就是对于树中任意的一个节点,左子树的高度-右子树的高度 =1/0/-1。、

而红黑树就是既满足的二叉平衡树的特性,又满足了二叉排序树的特性。

我们为什么要引入二叉平衡树和红黑树呢?

我们要从操作系统层面考虑,因为树的高度越高,磁盘I/O次数越多,查询的性能越低,所以要尽可能使树的高度越低越好。


关于红黑树的知识点还有很多很多,等下次整理出来以后再和大家分享!


谢谢观看,欢迎指正!


MySQL索引凭什么能让查询效率提高这么多?

IM即时通讯柠檬^ 发表了文章 • 1 个评论 • 148 次浏览 • 2020-09-07 10:26 • 来自相关话题

背景我相信大家在数据库优化的时候都会说到索引,我也不例外,大家也基本上能对数据结构的优化回答个一二三,以及页缓存之类的都能扯上几句,但是有一次阿里P9的一个面试问我:你能从计算机层面开始说一下一个索引数据加载的流程么?(就是想让我聊IO)我当场就去世了....... ...查看全部

背景

我相信大家在数据库优化的时候都会说到索引,我也不例外,大家也基本上能对数据结构的优化回答个一二三,以及页缓存之类的都能扯上几句,但是有一次阿里P9的一个面试问我:你能从计算机层面开始说一下一个索引数据加载的流程么?(就是想让我聊IO)

我当场就去世了....因为计算机网络和操作系统的基础知识真的是我的盲区,不过后面我恶补了,废话不多说,我们就从计算机加载数据聊起,讲一下换个角度聊索引。

正文

MySQL的索引本质上是一种数据结构

让我们先来了解一下计算机的数据加载。

磁盘IO和预读:

1.png

先说一下磁盘IO,磁盘读取数据靠的是机械运动,每一次读取数据需要寻道、寻点、拷贝到内存三步操作。

寻道时间是磁臂移动到指定磁道所需要的时间,一般在5ms以下;

寻点是从磁道中找到数据存在的那个点,平均时间是半圈时间,如果是一个7200转/min的磁盘,寻点时间平均是600000/7200/2=4.17ms;

拷贝到内存的时间很快,和前面两个时间比起来可以忽略不计,所以一次IO的时间平均是在9ms左右。听起来很快,但数据库百万级别的数据过一遍就达到了9000s,显然就是灾难级别的了。

2.png

考虑到磁盘IO是非常高昂的操作,计算机操作系统做了预读的优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。

每一次IO读取的数据我们称之为一页(page),具体一页有多大数据跟操作系统有关,一般为4k或8k,也就是我们读取一页内的数据时候,实际上才发生了一次IO。

(突然想到个我刚毕业被问过的问题,在64位的操作系统中,Java中的int类型占几个字节?最大是多少?为什么?)

那我们想要优化数据库查询,就要尽量减少磁盘的IO操作,所以就出现了索引。

索引是什么?

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。

MySQL 中常用的索引在物理上分两类,B-树索引和哈希索引。

本次主要讲BTree索引。

BTree索引

BTree又叫多路平衡查找树,一颗m叉的BTree特性如下:

树中每个节点最多包含m个孩子。

除根节点与叶子节点外,每个节点至少有[ceil(m/2)]个孩子(ceil()为向上取整)。

若根节点不是叶子节点,则至少有两个孩子。

所有的叶子节点都在同一层。

每个非叶子节点由n个key与n+1个指针组成,其中[ceil(m/2)-1] <= n <= m-1 。

3.png

这是一个3叉(只是举例,真实会有很多叉)的BTree结构图,每一个方框块我们称之为一个磁盘块或者叫做一个block块,这是操作系统一次IO往内存中读的内容,一个块对应四个扇区,紫色代表的是磁盘块中的数据key,黄色代表的是数据data,蓝色代表的是指针p,指向下一个磁盘块的位置。

来模拟下查找key为29的data的过程:

1、根据根结点指针读取文件目录的根磁盘块1。【磁盘IO操作1次】

2、磁盘块1存储17,35和三个指针数据。我们发现17<29<35,因此我们找到指针p2。

3、根据p2指针,我们定位并读取磁盘块3。【磁盘IO操作2次】

4、磁盘块3存储26,30和三个指针数据。我们发现26<29<30,因此我们找到指针p2。

5、根据p2指针,我们定位并读取磁盘块8。【磁盘IO操作3次】

6、磁盘块8中存储28,29。我们找到29,获取29所对应的数据data。

由此可见,BTree索引使每次磁盘I/O取到内存的数据都发挥了作用,从而提高了查询效率。

但是有没有什么可优化的地方呢?

我们从图上可以看到,每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小,当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。

B+Tree索引

B+Tree是在B-Tree基础上的一种优化,使其更适合实现外存储索引结构。在B+Tree中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点上只存储key值信息,这样可以大大加大每个节点存储的key值数量,降低B+Tree的高度。

4.png

B+Tree相对于B-Tree有几点不同:

非叶子节点只存储键值信息, 数据记录都存放在叶子节点中, 将上一节中的B-Tree优化,由于B+Tree的非叶子节点只存储键值信息,所以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亿 条记录。(这种计算方式存在误差,而且没有计算叶子节点,如果计算叶子节点其实是深度为4了)

我们只需要进行三次的IO操作就可以从10亿条数据中找到我们想要的数据,比起最开始的百万数据9000秒不知道好了多少个华莱士了。

而且在B+Tree上通常有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种链式环结构。所以我们除了可以对B+Tree进行主键的范围查找和分页查找,还可以从根节点开始,进行随机查找。

数据库中的B+Tree索引可以分为聚集索引(clustered index)和辅助索引(secondary index)。

上面的B+Tree示例图在数据库中的实现即为聚集索引,聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据,辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据,而是存储相应行数据的聚集索引键,即主键。

当通过辅助索引来查询数据时,InnoDB存储引擎会遍历辅助索引找到主键,然后再通过主键在聚集索引中找到完整的行记录数据。

不过,虽然索引可以加快查询速度,提高 MySQL 的处理性能,但是过多地使用索引也会造成以下弊端:

创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。

除了数据表占数据空间之外,每一个索引还要占一定的物理空间。如果要建立聚簇索引,那么需要的空间就会更大。

当对表中的数据进行增加、删除和修改的时候,索引也要动态地维护,这样就降低了数据的维护速度。

注意:索引可以在一些情况下加速查询,但是在某些情况下,会降低效率。

索引只是提高效率的一个因素,因此在建立索引的时候应该遵循以下原则:

在经常需要搜索的列上建立索引,可以加快搜索的速度。

在作为主键的列上创建索引,强制该列的唯一性,并组织表中数据的排列结构。

在经常使用表连接的列上创建索引,这些列主要是一些外键,可以加快表连接的速度。

在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,所以其指定的范围是连续的。

在经常需要排序的列上创建索引,因为索引已经排序,所以查询时可以利用索引的排序,加快排序查询。

在经常使用 WHERE 子句的列上创建索引,加快条件的判断速度。

现在大家知道索引为啥能这么快了吧,其实就是一句话,通过索引的结构最大化的减少数据库的IO次数,毕竟,一次IO的时间真的是太久了。。。

总结

就面试而言很多知识其实我们可以很容易就掌握了,但是要以学习为目的,你会发现很多东西我们得深入到计算机基础上才能发现其中奥秘,很多人问我怎么记住这么多东西,其实学习本身就是一个很无奈的东西,既然我们不能不学那为啥不好好学?去学会享受呢?最近我也在恶补基础,后面我会开始更新计算机基础和网络相关的知识的。


作者:敖丙,链接:https://juejin.im/post/6869532756498448392

数据库初探(1)————关于InnoDB和MyISAM两种数据库存储引擎

IM即时通讯刘沛栋 发表了文章 • 1 个评论 • 154 次浏览 • 2020-07-14 14:58 • 来自相关话题

1.mysql中最常见的两种数据库引擎InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。MyISAM存储引擎:MyISAM存... ...查看全部

1.mysql中最常见的两种数据库引擎

InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。


MyISAM存储引擎:MyISAM存储引擎在MYSQL5.1之前的版本是默认的存储引擎,它支持大量的特性,包括全文检索,压缩等,但是它不支持行级锁和事务,而且有一个很严重的缺点就是奔溃后无法安全恢复。

  

2.在弄清楚MyISAM和InnDB存储引擎之前,我们先来搞懂什么是表级锁,什么是行级锁,什么是页级锁?


表级锁:正如他的名字一样,是锁定整张表,是Mysql目前为止锁粒度最大的锁定机制。一个用户在对表进行写操作之前,回先获得写锁,这样会阻塞其他用户的读写操作,只有没有写锁的时候,用户才会获得读锁,但是读锁之间不相互阻塞。


优点:逻辑非常简单,因为是锁定整张表,所以获取锁和释放锁的速度非常快,还可以防止死锁的发生。

缺点:因为是锁定整张表,所以锁的共享资源非常多,在并发情况下性能比较低。

使用的场景:适合以查询为主,只有按少量索引条件更新数据的应用。

支持的存储引擎:MySAM和InnoDB


行级锁:正如它的名字一样,是锁定表中的一行数据,是Mysql目前为止锁粒度最小的锁定机制,仅对指定的数据加锁,这样其他进程也会对这张表中的其他数据进行操作。


优点:因为锁的粒度非常小,所以处理高并发场景会有优势

缺点:因为锁粒度比较小,所以获取锁和释放锁的时候就会比较慢,带来的性能开销也就大了,还容易造成死锁的现象,

使用的场景:适合以大量按索引条件并发更新少量数据,同时又有高并发查询的应用。

支持的存储引擎:InnoDB


页级锁:锁的粒度位于表级锁和行级锁


3.我们现在了解了什么是表级锁和什么是行级锁,同时我们知道了两种常用的存储引擎他们分别支持哪种粒度的锁,即MyISAM支持表级锁,InnoDB支持行级锁和页级锁,那么他们两种存储引擎具体有什么区别呢?


(1)首先我们说最重要的一点,就是MyISAM不支持事务,但是InnoDB支持事务。在使用InnoDB的时候,会默认将每一条sql语句都封装成事务,自动提交,这样会影响速度,所以最好把多条语句放在begin和commit之间,组成一个事务。

(2)InnoDB支持外键,但是MyISAM不支持外键。一个具有外键的InnoDB的表不能转化成MyISAM表。

(3)InnoDB不支持全文检索,但是MyISAM支持全文检索。在涉及全文检索的项目中MyISAM速度更快。PS:MyIsam在5.7以后也支持全文检索。

(4)InnoDB支持表级锁和行级锁,MyISAM支持表级锁。

(5)InnoDB必须有主键(没有的话会自动生成),MyISAM可以没有主键。

(6)InnoDB的索引是聚集索引,使用的是B+树的数据结构(后面会详细分析B+树和B树的数据结构)。聚集索引的意思是数据文件和主键索引(后面会详细讲)是捆绑在一起的,我们一般推荐使用主键索引,因为一次性查到数据文件这样的效率高,不推荐使用辅助索引(辅助索引中包含主键列),因为这样会先找到主键,再通过主键找到数据文件,就会进行两次查询。总的来说,就是主键索引存放的是数据文件,辅助索引存放的是主键的值。

MyISAM的索引是非聚集索引,使用的是B+树的数据结构。非聚集索引的意思是数据文件和索引是分开的(注意这里是索引,而不是主键索引,因为我们上面说过MyISAM可以没有主键索引),索引中存放的是数据文件的地址。

(7)表的具体行数,在MyISAM存储引擎中,保存有表的总行数,通过select count(*) from table直接取出。在InnoDB存储引擎中,没有保存表的行数,通过select count(*) from table会遍历整个表,性能消耗极大。在这里注意的一点就是,在加入where条件后,两种存储引擎的效率相同。


4.我们了解了两种存储引擎的区别,那么我们如何选择使用哪种存储引擎呢?

(1)看是否需要支持事务,如果不需要,则使用MyISAM,如果需要的话,就使用InnoDB。

(2)如果对数据库只有读的操作,建议使用MyISAM,如果对数据库的操作既有读又有写,那么建议使用InnoDB。


5.从上述的几个问题中我们大概了解到什么是MyISAM和InnoDB,那么面试中我们应该如何更好的向面试官谈呢?

我们应该先从这两种数据库存储引擎的优点开始分析,再谈到索引,然后谈到他们的应用场景:

InnoDB引擎,它提供了对数据库事务ACID的支持,行级锁和表级锁的支持,支持外键。

采用的是聚集索引,聚集索引的意思是叶节点data域保存了完整的数据记录,索引的key就是数据表的主键,因此InnoDB表数据文件本身就是主索引。除了主索引还有辅助索引,InnoDB的辅助索引的data域是主键。聚集索引推荐使用主键索引,因为这样查询速度比较快。

MYSQL运行的时候,InnoDB会在内存中创建缓冲池,用户缓冲数据以及索引,但是它的启动比较慢,并且没有保存表的行数。所以,这类引擎 当你需要数据库事务支持的时候,该引擎就是首选,由于锁的粒度比较小,写操作的时候不会锁定整张表,所以支持高并发的场景。事实上,InnoDB存储引擎现已是最主流的存储引擎。



MyISAM引擎,它不提供对数据库事务ACID的支持,它支持表级锁,不支持外键,所以它在写的时候,会锁定整张表,对表处理的性能就会变慢。

采用的是非聚集索引,非聚集索引指叶节点的data域保存的是数据文件的地址,而辅助索引和主索引没有什么区别,唯一的区别就是主索引的key是唯一的,辅助索引的key可以不唯一。

好处就是MyIsam保存了表的行数,在执行select count(*) from table 的时候,可以直接读取已经保存的值而不会遍历整张表,InnoDB存储引擎没有这一功能。

当数据库的读的操作多于写操作的时候,并且不要求事务的支持的时候,优先使用MyISAM存储引擎。


6.在上述问题中,我们频繁提到了索引,索引对于构建数据库有着至关重要的地位,那么什么是索引呢?

我们首先要清楚一点,如果我们合理的设计数据库并且合理的利用索引,会大大提升数据库检索的性能,但是如果我们滥用数据库的索引,反而会影响数据库的性能。

第一点是数据库的索引是利用空间换时间的策略,将数据的引用按照合适的数据结构进行存储就是我们所说的索引。第二点我们数据库的索引通常情况下使用的是B+树的数据结构,因为B+树非常适合文件系统查找。


7.上面的问题我们了解到了什么是索引,那么MyISAM和InnoDB的索引结构到底长什么样呢?我们分成主键索引和辅助索引来讨论。


我们来引用网络上的图来说明这个问题:

首先说MyISAM索引实现:

1.主键索引:

679616-20180115165534912-4452270.png

MyISAM为B+树的数据结构作为索引,从上图我们可以看出,叶子节点data域存储的是数据文件的地址,Col1为主键。

2.辅助索引:

2.png

在MyISAM存储引擎中,我们看到辅助索引和主键索引没有什么区别,只是主键索引要求key是唯一的,辅助索引的key可以是不唯一的,上图在col2上建立一个辅助索引。

我们可以看出,MyISAM存储引擎的索引策略:B+树叶子节点data域保存的是数据文件的地址,因此,MyISAM中索引检索的算法首先按照B+树搜索算法搜索索引,如果指定的key存在的话,就取出其data域的值,这个值是数据文件的地址,再通过打他域的地址,找到数据文件,因此,叫它非聚集索引,主要目的就是和聚集索引做一个区分。


我们再来讨论下InnoDB索引实现:

1.主键索引:

3.png

同样是B+树,但是实现方式确是不同的,InnoDB表数据文件本身就是一个索引结构,它的叶子节点data域保存了完整的数据记录,因为InnoDB的数据文件本身就是按照主键聚集,所以InnoDB表必须有主键,如果没有显示显示,则我们的数据库会自动的选择一个具有唯一标识列来作为主键,如果还是没有,则数据库自动创建一个主键列。

2.辅助索引:

4.png

上图中可以看出,InnoDB存储引擎所有辅助索引都是以主键作为Data域。

但是我们在检索的时候,InnoDB存储引擎推荐使用主键索引,因为这种聚聚索引的方式(主键上的都是自增的,所以范围查找的时候会更加快速)使得按照主键索引非常的高效。但是辅助索引需要检索两遍索引,首先辅助索引先找到主键索引,再通过主键索引找到数据文件。


不同存储引擎的索引实现对于我们正确使用和优化索引都非常有帮助,例如我们知道了InnoDB的索引实现以后,我们就知道了为什么不能用过长字段的值作为主键,因为辅助索引中包含主键索引,主键索引过长,就会导致辅助索引也过长。

还有一个例子就是使用非单调的字段作为主键在InnoDB中是不好的,因为InooDB数据文件本身就是一颗B+树,非单调的主键会造成数据文件一位要维持B+树的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键是一个很好的选择。


8.上面我们说了那两种存储引擎,我们直到B+树的数据结构用在索引中是最好的,我们在讨论B+树的时候,经常会讨论B树,那么B树和B+树有什么区别呢?

(1)B树的关键字分布在整棵树上,B+树的关键字分布在叶子节点上,且叶子节点的顺序本身就是自小到大有序的(链表形式)。

(2)查找过程虽然类似,但是B树的搜索有可能在非叶子节点上完成,B+树的搜索只能在叶子节点上完成,从根节点一直到叶子节点。

(3)B树在插入,删除的时候要进行不断的分类以及合并,会破坏B树的性质。

(4)B+树的非叶子节点相当于叶子节点的索引,叶子节点相当于存储系统的数据库。

(5)B+树比B树更适合数据库的索引,B树更适合文件系统的索引(如MangoDB)。


5.png

6.png

注:B+树有所演变,B+树在非叶子节点上添加了顺序访问指针,就在在每一个叶子节点上添加了指向下一个叶子节点的指针,提高了区间访问的性能。


9.我们了解了B+树和B树的优点的缺点后,那么为什么Mysql的存储引擎要使用B+树而不是使用B数呢?(面试常问)

从查询性能来看,因为B+树所有的数据文件都在叶子节点上,并且所有的叶子节点都是用指针互相连接。这时候,我们考虑一个业务场景,如果我们要从数据库中select多条数据,比如最后10条。如果我们使用B数,因为B树的非叶子节点也保存着数据文件,如果要查询,肯定有中序查找,这时候,我们势必要跨层查找。如果是B+树,因为B+树所有的数据都保存在叶子节点中,不用跨层,且有链表的形式,所以若能很快的找到首部元素,就能够很快的找到需要查找到的数据。


从操作系统层面来考虑,因为B树不管是叶子节点还是非叶子节点都要保存数据,这样就会使非叶子节点保存的指针数量变少,指针数量少的情况要保存大量的数据,就会使树的高度增加,一旦树的高度增加,就会使磁盘I/O的次数增加,查询性能就会变高。


10.hash存储索引的时间复杂度是O(1),B+树的时间复杂度是O(nlogn),那么为什么数据库的索引是B+树呢?(面试题常问)

这还是和我们的业务场景有关,如果我们查询单条数据,那么的确是hash索引的效率更高,但是我们在数据库中出现单条查询的情况少之又少,一般都是多条查询,使用B+树主键索引有序,且有链表的数据结构,就能很快查找出多条数据。

还有三个原因:

(1)索引一般保存在我们的硬盘中,可能不能一次性全部加载进内存中,而B+树的设计支持数据分批加载。

(2)使用B+树因为树的高度比较低,磁盘I/O的次数少,查询性能就会提高。

(3)再一个就是存在模糊查询的情况,哈希表是不支持模糊查询的,只能遍历整张表,而B+树可以采用最左前缀的原则进行查询找到相应的数据。


11.我们知道数据库的存储引擎一般采用的是B+树数据结构的索引,那么哪些是使用B树的数据结构呢?

MangoDB


12.为什么MangoDB采用的是B树的数据结构作索引的结构?

我们知道,索引的结构一般是红黑树,B树或者红黑树,因为这些树是多路树,使用多路数,可以降低树的高度。

文件系统(MangoDB)和数据库的索引都是存放在硬盘中,并且数据量很大的情况,就不能一次性加载进内存,如果是红黑树,就不能保证一次性都加载进内存,所以使用B树的结构,我们每次加载B树的一个节点,然后一步一步加载。

假设内存中每次只能加载两个字节的数据,那么长的有序数组无法一次性全部加载,要是我们设计成一个3路的B 树,那么一个节点最多有两个数,查找的时候,每次加载进一个节点就可以了。

如果是在内存中,红黑树比B树的效率更高,如果实在硬盘中保存,那么B树更优。


13.我们上面提到了红黑树,那么到底什么是红黑树呢?

我们知道,二叉排序树就是节点的左孩子的值小于该节点的值,该节点的右孩子的值大于该节点的值。那么在一些极端情况下,会出现链表的情况。这时候,我们就引入了平衡而二叉树的概念,平衡二叉树的意思就是对于树中任意的一个节点,左子树的高度-右子树的高度 =1/0/-1。、

而红黑树就是既满足的二叉平衡树的特性,又满足了二叉排序树的特性。

我们为什么要引入二叉平衡树和红黑树呢?

我们要从操作系统层面考虑,因为树的高度越高,磁盘I/O次数越多,查询的性能越低,所以要尽可能使树的高度越低越好。


关于红黑树的知识点还有很多很多,等下次整理出来以后再和大家分享!


谢谢观看,欢迎指正!