【从入门到入土】令人脱发的数据库底层设计

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 【从入门到入土】令人脱发的数据库底层设计

点击上方“Java知音”,选择“置顶公众号”

技术文章第一时间送达!

作者:ObjectSpace

juejin.im/post/5d6f3efde51d4561fd6cb548

juejin.im/post/5d6f3efde51d4561fd6cb548

前言

说到数据库这个词,我只能用爱恨交加这个词来形容它。两年前在自己还单纯懵懂的时候进了数据库的课堂,听完数据库的课,觉得这是一门再简单不过的课程,任何一门编程语言都比SQL要晦涩难懂,任何一门理论课程都比数据库关系要复杂得多。

直到从被面试官按在地上摩擦,到工作中那一条条令人发指的慢查询SQL,这就已经完全颠覆了我对数据库的看法。

在有各种数据库工具的今天,我们是看不到那简单到不能再简单的一张表的背后,隐藏着多少数据结构的支撑,也看不到我们随手敲的一条SELECT,背后会有多少算法和数据结构在给我们做优化,作为一个有技术热情的coder,应该需要对我们每日在用的数据库做一次深入了解。

数据库架构

如何设计一个关系型数据库

这个问题很宽泛,需要我们对于整体有一个掌控,对我们平时所用的数据库要有足够的了解,对整个数据库做模块划分是这道题的关键,这就更需要我们足够了解数据库,对数据库做一个合理的模块设计。

设计

从开始,首先要明白,数据库的最最根本的作用是什么——存储数据,所以我们需要一个存储模块来存储我们的数据,它可以是一个文件系统(机械硬盘?SSD固态硬盘?)。但光有存储模块是不够的,我们还需要一个程序实例,来组织或者获取这些数据,在程序实例中我们需要提供获取和组织这些数据的方式,所以我们需要在程序实例中实现存储管理模块。

我们还可以在存储管理模块中做一些提升效能的工作,例如同时读取多行、分块分页存储等。数据库作为一款对性能要求极高的软件,我们应该加入缓存机制,来提高其速度,当查询到缓存中已存在的数据,我们应该直接将其从缓存中读取,这样可以减少硬盘IO次数,提高效能。

到这里为止,我们已经完成了对数据库的存储方面的功能设计,但是作为数据库,应该需要提供给用户对数据进行增删改查的接口,即平时所写的SQL,所以我们应该提供一个SQL解析模块,来对日常用户所写的SQL语句进行解析,转换成机器可识别的指令,我们也可以直接将编译过的SQL加入缓存,下次再有同样的SQL就直接从缓存中读取,同样可以提高效能。

作为一款成熟的数据库,需要应对各种复杂的环境,要时刻记录数据库的状态,所以我们还需要一个日志管理模块,对操作和错误信息进行记录。数据库中需要支持多用户操作,但每个用户都能操作所有的数据,这是不现实的,所以还需要权限划分模块对数据库用户进行权限管理。

当然数据库说到底也只是一款软件,是软件就会有bug,就会出故障,故障不可怕,可怕的是在数据库这种敏感软件下对故障没有特殊的处理方式,导致数据丢失,毕竟数据是无价的,所以数据库应该引入容灾机制,在数据库挂了的时候,对数据进行恢复。

还有作为数据库最重要的两个模块,也是现今任何一个数据库都需要考虑的问题——并发和查找效率,所以还需引入索引和锁这两个模块,这就是实现一个最基础的数据库所必需的几大模块。

归纳

综上对数据库设计模块做一个汇总:

1.存储模块

2.程序实例

  • 存储管理模块
  • 缓存机制
  • SQL解析模块
  • 日志管理模块
  • 权限划分模块
  • 容灾机制
  • 索引模块
  • 锁模块
  • 【从入门到入土】令人脱发的数据库底层设计

    索引

    为什么要使用索引

    要考虑这个问题,首先要从最基础的查找表中数据的过程开始说起。通常我们在查找一个序列中的某一个元素时,用到的最简单的方式就是遍历,数据库也是一样,在一张表中查找某一行数据时,如果不考虑索引的状况下,也会采用一个逐行扫描的方式,只不过数据库通常以块或者页为单位,所以它通常将整个块或者页加载进内存,然后逐块轮询查找到结果并返回。

    如果数据库中只有少量数据,那么进行全表扫描,速度还是会很快,但是如果在数据量很大的表中,这种方法就不再适用了,在数据量很大的表中,由于逐行扫描代价变大,通常需要避免采用这种逐行扫描的方式进行数据查找,数据库为了使查询变得高效,所以引入了索引这种方式对数据进行查找。

    什么样的信息能成为索引

  • 主键
  • 唯一键
  • 普通键
  • 索引的数据结构

    二叉查找树

    众所周知,二叉查找树是每个节点最多由两个子树的树结构,而其还有一个特点是,在任意一颗树中,根节点的左孩子永远小于根节点,根节点的右孩子永远大于根节点,用二叉查找树作为索引,确实可以提高查找效率,其可以使用二分查找将时间复杂度控制在O(lgn),但是二叉查找树有一个显而易见的缺陷,当某种特殊情况(按照某个特定顺序插入树)发生时,二叉查找树将变为下图右侧(线性二叉树)的状况:

    【从入门到入土】令人脱发的数据库底层设计

    此时二叉查找树查找任意某个元素时,其查找顺序与逐行查找无异,查询时间复杂度又将回到O(n),查询效率无法保持。

    B-Tree

    B-Tree,平衡多路查找树,如果每个节点,最多有N个孩子,那么这样的树就叫N阶B-Tree,
    每个节点中主要包含关键字和指向孩子的指针,最多能有几个孩子,取决于节点的容量和数据库的相关配置,通常情况下这个N是很大的。

    B-Tree作为一种数据结构,有如下特征:

  • 根节点至少包含两个孩子
  • 树中每个节点至多含有N个孩子(N=2)
  • 除根节点和叶节点外,其它每个节点至少有ceil(N/2)个孩子。(ceil表示取上限,例如1.2的上限为2,1.1的上限也为2,非四舍五入)
  • 所有叶子节点都位于同一层,即叶子节点的高度都是一样的。
  • 假设每个非终端节点包含n个关键字信息(P0,P1…Pn,k1…kn)
  • 1、ki(i=1..n)为关键字,且关键字按顺序升序排序k(i-1)ki。 2、关键字的个数必须满足:[ceil(m/2)-1]=n=m-1]。 3、非叶子节点的指针:P[1],P[2]…P[M];其中P[1]指向关键字小于K[1]的子树,P[N]指向关键字大于K[N-1]的子树,其它P[i]指向关键字属于(K[i-1],K[i])的子树。

    【从入门到入土】令人脱发的数据库底层设计

    遵守上述规则,其目的就是尽量使每个索引块都尽可能多的存储数据,尽可能减少查找次数以提升效率。

    举个例子,模拟一下查找过程,以便于理解:假设我们要查询关键字为10的数据,则从根节点出发,1017,于是通过P1进入其孩子节点,108且1012,于是通过P2进入其孩子节点,最后寻找到10。如果不使用索引,而使用逐行扫描的方式进行查找,则从0开始至少扫描10次才能查找到10号数据,有了索引之后可以看到,查找次数从10变为3,大大提高了查找效率。

    如果这里是二叉查找树,会出现极端情况,使得查找时间复杂度为O(n),而如果是B-Tree,由于上述五个约束,可以让节点通过合并、分裂、上移、下移等操作,使得树高度较二叉查找树小,查找效率显然更高。

    B+ -Tree(MySQL)

    B+ -Tree是B-Tree的一个变体,其定义基本与B树相同,除了:

  • 非叶子节点的子树指针与关键字个数相同,其表明B+树能存储更多的关键字
  • 非叶子节点的子树指针P[i],指向关键字值[K[i],K[i+1])的子树。
  • 非叶子节点仅用来做索引,数据到保存在叶子节点中。(B+树的所有检索都是从根部开始,直到搜索到叶子节点结束。)
  • 所有叶子节点均有一个链指针,指向下一个叶子节点。(方便直接在叶子节点直接做范围统计)
  • 【从入门到入土】令人脱发的数据库底层设计

    B+树相较于B树的优势:****

  • B+树的磁盘读写代价更低。
  • B+树的查询效率更加稳定。
  • B+树更有利于对数据库的扫描。
  • Hash

    Hash索引是根据Hash结构的定义,只需要一次运算便可以找到数据所在位置,不像B+树或者B树需要从根结点出发寻找数据,所以Hash索引的查询效率理论上要高于B+树索引,但是MySQL中并没有采用这一种索引,这是由于这种索引除查询效率之外的缺陷是十分明显的。

  • 仅仅只能满足"=","IN",不能使用范围查询。由于其是由Hash运算获取的数据存放位置,每次Hash运算获取的是一个确定的值,且这个值并不与数据本身的大小有关系,所以其并不能满足范围查询。
  • 无法被用来避免数据的排序操作。和1的意思差不多,Hash的索引值是由Hash运算获取的,其索引值与数据本身的大小并无明显关系。
  • 不能利用部分索引键查询。
  • 不能避免表扫描。由于Hash索引会产生Hash冲突,存在Hash冲突的数据会被连接到同一个链表上,当大量数据被连接到相同链表上时,查询某条数据就变成了扫描该链表,时间复杂度并不能保证在O(1)。
  • 遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。
  • BitMap索引

    位图索引,当表中的某个字段只有几种值的时候,例如:性别,此时用位图索引是一个最佳的选择。目前使用位图索引的比较主流的数据库有Oracle数据库。

    密集索引和稀疏索引的区别

  • 密集索引文件中的每个搜索码都对应一个索引值,稀疏索引文件只为索引码的某些值建立索引项。
  • 密集索引将数据存储与索引放到了一块,找到索引也就找到了数据,稀疏索引将数据和索引分开存储,索引结构的叶子节点指向数据的对应行。
  • 关于MySQL的MyISAM和InnoDB

    MyISAM不论是主键索引、唯一键索引、还是普通索引,都采用的是稀疏索引,而InnoDB必须有且仅有一个密集索引。

    InnoDB密集索引规则:

  • 若一个主键被定义,该主键则作为密集索引。
  • 若没有主键被定义,该表的第一个唯一非空索引则作为密集索引。
  • 若不满足以上条件,InnoDB内部会生成一个隐藏主键(密集索引)。
  • 非主键索引存储相关键位和其对应的主键值,包含两次查找。
  • 注:InnoDB如果查询条件为主键索引,则只需查询一次,但是辅助索引需要查询两次,先通过辅助索引查询到主键索引,再查询到数据。

    【从入门到入土】令人脱发的数据库底层设计

    从上图中可以看到,如果一个索引是聚集索引,则其叶子节点上存放的即是数据本身,而如果一个索引是稀疏索引,叶子节点存放的仅是地址,指向将要查找的数据。

    如何定位并优化慢查询SQL

    首先先建立一张表

    
    CREATE DATABASE sqltest;
    use sqltest;
    create table tb_test(
      test_id int primary key auto_increment,
      test_name varchar(1024),
      test_date datetime,
      test_desc varchar(1024)
    );
    

    在这张表中灌入200w数据。

    【从入门到入土】令人脱发的数据库底层设计

    1.根据慢日志定位慢查询SQL

    
    #查找慢日志
    slow_query_log
    
    【从入门到入土】令人脱发的数据库底层设计

    记录慢日志SQL运行时间阈值

    【从入门到入土】令人脱发的数据库底层设计

    设置慢查询阈值为1秒,重连数据库  set global long_query_time = 1;

    【从入门到入土】令人脱发的数据库底层设计

    制造慢查询:

    【从入门到入土】令人脱发的数据库底层设计 【从入门到入土】令人脱发的数据库底层设计

    2.使用explain工具分析SQL  explain select test_name from tb_test order by test_name desc

    <img class="">

    type:找到数据的方式,根据效率从高到低排序有如下几种

    systemconsteq_refreffulltextref_or_nullindex_mergeunique_subqueryindex_subqueryrangeindexall

    如果type为index或all,表示本次扫描为全表扫描,说明这个语句是需要优化的。

    extra:可以用来辅助type帮助我们进行SQL优化,extra中出现以下两项,意味着MySQL根本不能使用索引,效率会受到重大影响,应该尽可能对此进行优化。

    **Using filesort:**表示MySQL会对结果使用一个外部索引排序,而不是从表里按索引次序读到相关内容,可能在内存或者磁盘上进行排序。MySQL中无法例用索引完成的排序操作称为“文件排序”。

    **Using temporary:**表示MySQL在对查询结果排序时使用临时表,常见于排序 order by和分组查询group by。

    3.修改SQL,尽量让SQL走索引

    我们可以知道,创建表时,我们将id设为主键,那么id也就自然称为了索引,所以我们只要修改排序字段为id,即可以通过索引排序。

    
    explain select test_id from tb_test order by test_id desc
    
    【从入门到入土】令人脱发的数据库底层设计

    **key:**PRIMARY 代表使用了主键索引

    【从入门到入土】令人脱发的数据库底层设计

    另一种情况,在特定状况下一定需要使用name进行排序,那还有一种做法,就是将name字段加索引。

    
    #加索引
    ALTER TABLE tb_test add index index_name(test_name);
    #再次分析
    explain select test_name from tb_test order by test_name desc;
    

    结果:

    【从入门到入土】令人脱发的数据库底层设计

    联合索引的最左匹配原则的成因

    上文中只是用了单一索引对表进行排序,如果使用联合索引又会是什么样的一种状况?
    最左匹配原则:假设数据表中有两列,A and B,我们将A、B设置为联合索引,然后在where语句中调用where A = ? AND B = ?,该查询语句会使用AB联合索引,调用where A = ?,该查询语句也会使用AB联合索引,但当调用where B = ?时,它将不会使用AB联合索引。

    官方定义:

    1.最左前缀匹配原则,MySQL会一直向右匹配直到遇到范围查询(、、between、like)就停止匹配,比如 a=3 and b=4 and c5 and d=6,如果建立(a,b,c,d)顺序的索引,d是无法使用索引的,如果建立(a,b,d,c)的索引则都可以使用到,a、b、d的顺序可以任意调整。 2.=和in可以乱序,比如 a=1 and b=2 and c=3 建立(a,b,c)索引可以任意顺序,MySQL的查询优化器会帮你优化成索引可以识别的形式。

    索引是建立的越多越好吗

    答:NO,数据量小的表不需要建立索引,建立会增加额外的索引开销。另外数据变更需要维护索引,因此更多的索引意味着更多的维护成本。更多的索引还需要消耗更多的空间。

    锁 and 锁 and 锁

    MyISAM与InnoDB关于锁方面的区别是什么

  • MyISAM默认使用表级锁,不支持行级锁。
  • InnoDB默认使用行级锁,也支持表级锁。
  • InnoDB在使用索引时,默认使用行级锁,但当其没有用到索引时,默认使用表级锁。

    表级锁

    当一条数据库语句对某条数据进行操作时,默认将整张表进行加锁,其余操作无法对表进行更改,需等到当前操作执行完毕释放锁后,才能对该表进行更改。

    行级锁

    当一条数据库语句对某条数据或多条数据进行操作时,默认将正在操作的这几条数据进行加锁,其余操作无法对当前语句正在操作的这几条数据进行操作,但可以操作其他数据。

    共享锁和排他锁

    共享锁:当对某行或某张表上了共享锁之后,其它任意语句依然支持上共享锁,但不支持上排他锁。(MySQL使用lock in share mode加共享锁)

    排他锁:当对某行或某张表上了排他锁之后,其它任意语句对这一行或者这一张表进行读或写都是不允许的。(MySQL使用 for update 加排他锁)

    乐观锁和悲观锁

    悲观锁:总是假设最坏的情况,认为竞争总是存在,认为每次对数据的修改总会产生冲突,因此每次都会先上锁,其他线程阻塞等待释放锁。

    乐观锁:总是假设最好的情况,认为竞争总是不存在,认为每次对数据的修改都不会产生冲突,因此不会先上锁,再最后更新的时候,比较数据是否已经被更新,可用版本号或CAS实现。

    行级锁一定比表级锁优吗?

    答:不一定,锁的粒度越细,其消耗的资源代价越高。行级锁在上锁的时候需要扫描到某行再进行上锁,这样的代价是较大的。

    MyISAM和InnoDB各自适合的场景

    MyISAM适合的场景:

  • 频繁执行全表count语句。
  • 对数据进行增删改的频率不高,查询非常频繁。
  • 没有事务
  • InnoDB适合的场景:

  • 数据增删改查都相当频繁。
  • 可靠性要求比较高,存在事务。
  • 数据库事务四大特性ACID

    事务:作为单个逻辑单元执行的一个操作,要么全部完成,要么全部失败。

    原子性

    事务包含的所有操作,要么全部执行,要么全部失败。

    隔离性

    多个事务并发执行时,一个事务的执行不应该影响其它事务的执行。

    一致性

    事务应保证数据库状态从一个一致性状态转换到另一个一致性状态。(一致性状态:数据库的数据应满足完整性约束)

    持久性

    一个事务一旦提交,它的数据应该永久地保存在数据库中。

    事务隔离级别以及各级别下的并发访问问题

  • 更新丢失:一个事务的更新,引起另一个事务提交的丢失,MySQL所有事务隔离级别在数据库层面上均可避免。
  • 脏读:一个事务读到另一个事务未提交的数据,READ-COMMITTED事务隔离级别以上可避免。(ORACLE默认隔离级别为READ-COMMITTED)
  • 不可重复读:事务A多次读取同一数据时,事务B修改该数据,导致事务A每次读取到的数据结果不一致,REPEATABLE-READ隔离级别下可避免。
  • 幻读:事务A多次读取同一数据时,事务B对事务A的影响区间内进行增删操作,导致事务A读取到的数据一会多、一会少,就像产生幻觉了一样。SERIALIZABLE事务隔离级别可避免。(但实际上MySQL的InnoDB在REPEATABLE-READ隔离级别下避免了幻读的发生)
  • 【从入门到入土】令人脱发的数据库底层设计

    InnoDB可重复读隔离级别下如何避免幻读

    表象

    快照读(非阻塞读)–伪MVCC。使用此种机制避免使我们看到“幻行”。

    当前读:select …lock in share mode,select …for update,update,delete,insert.即加了锁的增删改查语句。由于其读取的是记录的最新版本,所以称为当前读。

    快照读:不加锁的非阻塞读(非SERIALIZABLE),select。基于提升并发性能的考虑,基于多版本并发控制。既然是基于多版本,也就是说快照读有可能读到非最新版本的数据。

    内在

    next-key锁(行锁+gap锁):next-key锁由两部分组成,行锁+gap锁,行锁即对单个行记录上的锁。Gap锁,即对插入索引间的空隙上锁,即锁定一个范围,但不包括记录本身。

    Gap锁的目的,是为了防止一个记录两次当前读出现幻读的情况。Gap锁只存在与Read-Committed(不包括Read-committed)以上的隔离级别存在。如果查询时,where条件全部命中(精确查询时),则不会用Gap锁,只会加记录锁。

    因为在精确查询的状况下,即使在读结果集的过程中,另一个事务增加一条数据,也不会增加到当前结果集下,只会在where条件的范围之外,所以并不会产生幻读现象,加行锁就足够了。如果where条件部分命中或者全不命中,则会加Gap锁。

    RC、RR级别下的InnoDB的非阻塞读(快照读)如何实现

    1.数据行里的DB_TRX_ID、DB_ROLL_PTR、DB_ROW_ID字段,DB_TRX_ID标识最近一次对本行记录做修改的事务ID,DB_ROLL_PTR回滚指针,当事务回滚时,去往undo日志寻找上一版本的数据,DB_ROW_ID行号(MySQL自动创建的隐藏自增主键)。

    2.undo日志:存储历史版本的数据。当某行的某个字段进行修改时,首先用排他锁锁住该行,然后将该行数据拷贝一份放入undolog中,通过行中的DB_ROLL_PTR指针,指向undolog中的这条数据,然后修改当前行的值,并填写DB_TRX_ID字段为当前事务的ID。

    3.read view:可见性判断。决定当前事务能看到的是哪个版本的数据。

    【从入门到入土】令人脱发的数据库底层设计

    结语

    令人头秃。

    推荐阅读(点击即可跳转阅读)

    1.

    2.

    3.

    4.

    5.

    觉得不错?欢迎转发分享给更多人

    【从入门到入土】令人脱发的数据库底层设计

    我知道你 “在看【从入门到入土】令人脱发的数据库底层设计

    原文始发于微信公众号(Java知音):

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

    转载声明:转载请注明出处,本技术博客是本人原创文章

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

    原文链接:blog.ouyangsihai.cn >> 【从入门到入土】令人脱发的数据库底层设计


     上一篇
    后端开发必备的 MySQL 日志文件知识点 后端开发必备的 MySQL 日志文件知识点
    点击上方“后端技术精选”,选择“置顶公众号” 技术文章第一时间送达! 作者:pjmike_pj juejin.im/post/5b7c0aabf265da438415b9eb juejin.im/post/5b7c0aabf
    下一篇 
    MySQL中update修改数据与原数据相同会再次执行吗? MySQL中update修改数据与原数据相同会再次执行吗?
    点击上方“后端技术精选”,选择“置顶公众号” 技术文章第一时间送达! 作者:powdba https://yq.aliyun.com/articles/694162 https://yq.aliyun.com/article