Object's Blog

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

字数统计: 6.1k阅读时长: 21 min
2019/09/04 分享

前言

说到数据库这个词,我只能用爱恨交加这个词来形容它。两年前在自己还单纯懵懂的时候进了数据库的课堂,听完数据库的课,觉得这是一门再简单不过的课程,任何一门编程语言都比SQL要晦涩难懂,任何一门理论课程都比数据库关系要复杂得多。直到从被面试官按在地上摩擦,到工作中那一条条令人发指的慢查询SQL,这就已经完全颠覆了我对数据库的看法。在有各种数据库工具的今天,我们是看不到那简单到不能再简单的一张表的背后,隐藏着多少数据结构的支撑,也看不到我们随手敲的一条SELECT,背后会有多少算法和数据结构在给我们做优化,作为一个有技术热情的coder,应该需要对我们每日在用的数据库做一次深入了解。

数据库架构

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

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

  • 设计

    从开始,首先要明白,数据库的最最根本的作用是什么——存储数据,所以我们需要一个存储模块来存储我们的数据,它可以是一个文件系统(机械硬盘?SSD固态硬盘?)。但光有存储模块是不够的,我们还需要一个程序实例,来组织或者获取这些数据,在程序实例中我们需要提供获取和组织这些数据的方式,所以我们需要在程序实例中实现存储管理模块。我们还可以在存储管理模块中做一些提升效能的工作,例如同时读取多行分块分页存储等。数据库作为一款对性能要求极高的软件,我们应该加入缓存机制,来提高其速度,当查询到缓存中已存在的数据,我们应该直接将其从缓存中读取,这样可以减少硬盘IO次数,提高效能。到这里为止,我们已经完成了对数据库的存储方面的功能设计,但是作为数据库,应该需要提供给用户对数据进行增删改查的接口,即平时所写的SQL,所以我们应该提供一个SQL解析模块,来对日常用户所写的SQL语句进行解析,转换成机器可识别的指令,我们也可以直接将编译过的SQL加入缓存,下次再有同样的SQL就直接从缓存中读取,同样可以提高效能。作为一款成熟的数据库,需要应对各种复杂的环境,要时刻记录数据库的状态,所以我们还需要一个日志管理模块,对操作和错误信息进行记录。数据库中需要支持多用户操作,但每个用户都能操作所有的数据,这是不现实的,所以还需要权限划分模块对数据库用户进行权限管理。当然数据库说到底也只是一款软件,是软件就会有bug,就会出故障,故障不可怕,可怕的是在数据库这种敏感软件下对故障没有特殊的处理方式,导致数据丢失,毕竟数据是无价的,所以数据库应该引入容灾机制,在数据库挂了的时候,对数据进行恢复。还有作为数据库最重要的两个模块,也是现今任何一个数据库都需要考虑的问题——并发和查找效率,所以还需引入索引这两个模块,这就是实现一个最基础的数据库所必需的几大模块。

  • 归纳

    综上对数据库设计模块做一个汇总:
    1.存储模块
    2.程序实例
    2.1存储管理模块
    2.2缓存机制
    2.3SQL解析模块
    2.4日志管理模块
    2.5权限划分模块
    2.6容灾机制
    2.7索引模块
    2.8锁模块
    设计数据库模块.

索引

  • 为什么要使用索引

    要考虑这个问题,首先要从最基础的查找表中数据的过程开始说起。通常我们在查找一个序列中的某一个元素时,用到的最简单的方式就是遍历,数据库也是一样,在一张表中查找某一行数据时,如果不考虑索引的状况下,也会采用一个逐行扫描的方式,只不过数据库通常以块或者页为单位,所以它通常将整个块或者页加载进内存,然后逐块轮询查找到结果并返回。如果数据库中只有少量数据,那么进行全表扫描,速度还是会很快,但是如果在数据量很大的表中,这种方法就不再适用了,在数据量很大的表中,由于逐行扫描代价变大,通常需要避免采用这种逐行扫描的方式进行数据查找,数据库为了使查询变得高效,所以引入了索引这种方式对数据进行查找。

  • 什么样的信息能成为索引

    1.主键、唯一键、普通键

  • 索引的数据结构

    • 二叉查找树

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

    • B-Tree

      B-Tree,平衡多路查找树,如果每个节点,最多有N个孩子,那么这样的树就叫N阶B-Tree,
      每个节点中主要包含关键字指向孩子的指针,最多能有几个孩子,取决于节点的容量和数据库的相关配置,通常情况下这个N是很大的。
      B-Tree作为一种数据结构,有如下特征:
      1.根节点至少包含两个孩子
      2.树中每个节点至多含有N个孩子(N>=2)
      3.除根节点和叶节点外,其它每个节点至少有ceil(N/2)个孩子。(ceil表示取上限,例如1.2的上限为2,1.1的上限也为2,非四舍五入
      4.所有叶子节点都位于同一层,即叶子节点的高度都是一样的。
      5.假设每个非终端节点包含n个关键字信息(P0,P1…Pn,k1…kn)

      ( a )ki(i=1..n)为关键字,且关键字按顺序升序排序k(i-1)<ki。
      ( b )关键字的个数必须满足:[ceil(m/2)-1]<=n<=m-1]。
      ( c )非叶子节点的指针:P[1],P[2]…P[M];其中P[1]指向关键字小于K[1]的子树,P[N]指向关键字大于K[N-1]的子树,其它P[i]指向关键字属于(K[i-1],K[i])的子树。

      B-Tree
      遵守上述规则,其目的就是尽量使每个索引块都尽可能多的存储数据,尽可能减少查找次数以提升效率。
      举个例子,模拟一下查找过程,以便于理解:假设我们要查询关键字为10的数据,则从根节点出发,10<17,于是通过P1进入其孩子节点,10>8且10<12,于是通过P2进入其孩子节点,最后寻找到10。如果不使用索引,而使用逐行扫描的方式进行查找,则从0开始至少扫描10次才能查找到10号数据,有了索引之后可以看到,查找次数从10变为3,大大提高了查找效率。
      如果这里是二叉查找树,会出现极端情况,使得查找时间复杂度为O(n),而如果是B-Tree,由于上述五个约束,可以让节点通过合并、分裂、上移、下移等操作,使得树高度较二叉查找树小,查找效率显然更高。

    • B+ -Tree(MySQL)

      B+ -Tree是B-Tree的一个变体,其定义基本与B树相同,除了:
      1.非叶子节点的子树指针与关键字个数相同,其表明B+树能存储更多的关键字
      2.非叶子节点的子树指针P[i],指向关键字值[K[i],K[i+1])的子树。
      3.非叶子节点仅用来做索引,数据保存在叶子节点中。(B+树的所有检索都是从根部开始,直到搜索到叶子节点结束。)
      4.所有叶子节点均有一个链指针,指向下一个叶子节点。(方便直接在叶子节点直接做范围统计)

      B+Tree.
      B+树相较于B树的优势:
      1.B+树的磁盘读写代价更低。
      2.B+树的查询效率更加稳定。
      3.B+树更有利于对数据库的扫描。

    • Hash

      Hash索引是根据Hash结构的定义,只需要一次运算便可以找到数据所在位置,不像B+树或者B树需要从根结点出发寻找数据,所以Hash索引的查询效率理论上要高于B+树索引,但是MySQL中并没有采用这一种索引,这是由于这种索引除查询效率之外的缺陷是十分明显的。
      1.仅仅只能满足”=”,”IN”,不能使用范围查询。由于其是由Hash运算获取的数据存放位置,每次Hash运算获取的是一个确定的值,且这个值并不与数据本身的大小有关系,所以其并不能满足范围查询。
      2.无法被用来避免数据的排序操作。和1的意思差不多,Hash的索引值是由Hash运算获取的,其索引值与数据本身的大小并无明显关系。
      3.不能利用部分索引键查询。
      4.不能避免表扫描。由于Hash索引会产生Hash冲突,存在Hash冲突的数据会被连接到同一个链表上,当大量数据被连接到相同链表上时,查询某条数据就变成了扫描该链表,时间复杂度并不能保证在O(1)。
      5.遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

    • BitMap索引

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

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

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

    • 关于MySQL的MyISAM和InnoDB
      MyISAM不论是主键索引、唯一键索引、还是普通索引,都采用的是稀疏索引,而InnoDB必须有且仅有一个密集索引。
      InnoDB密集索引规则:
      1.若一个主键被定义,该主键则作为密集索引。
      2.若没有主键被定义,该表的第一个唯一非空索引则作为密集索引。
      3.若不满足以上条件,InnoDB内部会生成一个隐藏主键(密集索引)。
      4.非主键索引存储相关键位和其对应的主键值,包含两次查找。
      :InnoDB如果查询条件为主键索引,则只需查询一次,但是辅助索引需要查询两次,先通过辅助索引查询到主键索引,再查询到数据。
      聚簇索引和非聚簇索引
      从上图中可以看到,如果一个索引是聚集索引,则其叶子节点上存放的即是数据本身,而如果一个索引是稀疏索引,叶子节点存放的仅是地址,指向将要查找的数据。
  • 如何定位并优化慢查询SQL

    首先先建立一张表

    1
    2
    3
    4
    5
    6
    7
    8
    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

    1
    2
    #查找慢日志
    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

    explain工具
    type:找到数据的方式,根据效率从高到低排序有如下几种 system>const>eq_ref>ref>fulltext>ref_or_null>index_merge>unique_subquery>index_subquery>range>index>all
    如果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字段加索引。

    1
    2
    3
    4
    #加索引
    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 c>5 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关于锁方面的区别是什么

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

    • 表级锁

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

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

      共享锁:当对某行或某张表上了共享锁之后,其它任意语句依然支持上共享锁,但不支持上排他锁。(MySQL使用lock in share mode加共享锁)
      排他锁:当对某行或某张表上了排他锁之后,其它任意语句对这一行或者这一张表进行读或写都是不允许的。(MySQL使用 for update 加排他锁)
    • 乐观锁和悲观锁

      悲观锁:总是假设最坏的情况,认为竞争总是存在,认为每次对数据的修改总会产生冲突,因此每次都会先上锁,其他线程阻塞等待释放锁。
      乐观锁:总是假设最好的情况,认为竞争总是不存在,认为每次对数据的修改都不会产生冲突,因此不会先上锁,再最后更新的时候,比较数据是否已经被更新,可用版本号或CAS实现。
    • 行级锁一定比表级锁优吗?

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

      MyISAM适合的场景:1.频繁执行全表count语句。2.对数据进行增删改的频率不高,查询非常频繁。3.没有事务
      InnoDB适合的场景:1.数据增删改查都相当频繁。2.可靠性要求比较高,存在事务。
  • 数据库事务四大特性ACID

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

    • 原子性

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

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

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

      一个事务一旦提交,它的数据应该永久地保存在数据库中。
  • 事务隔离级别以及各级别下的并发访问问题

    1.更新丢失 —— 一个事务的更新,引起另一个事务提交的丢失,MySQL所有事务隔离级别在数据库层面上均可避免。
    2.脏读 —— 一个事务读到另一个事务未提交的数据,READ-COMMITTED事务隔离级别以上可避免。(ORACLE默认隔离级别为READ-COMMITTED)
    3.不可重复读——事务A多次读取同一数据时,事务B修改该数据,导致事务A每次读取到的数据结果不一致,REPEATABLE-READ隔离级别下可避免。
    4.幻读——事务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。
    RCRR级别下非阻塞读
    3.read view:可见性判断。决定当前事务能看到的是哪个版本的数据。

结语

令人头秃。

本文图片来自网络,侵删。

欢迎大家访问我的个人博客:Object’s Blog

原文作者:Object

原文链接:http://blog.objectspace.cn/2019/09/04/【从入门到入土】令人脱发的数据库底层设计/

发表日期:2019 September 4th, 8:28:01 am

更新日期:2019 September 27th, 1:45:28 pm

版权声明:未经作者授权请勿转载

目录
  1. 1. 前言
  2. 2. 数据库架构
    1. 2.1. 如何设计一个关系型数据库
    2. 2.2. 设计
    3. 2.3. 归纳
  3. 3. 索引
    1. 3.1. 为什么要使用索引
    2. 3.2. 什么样的信息能成为索引
    3. 3.3. 索引的数据结构
      1. 3.3.1. 二叉查找树
      2. 3.3.2. B-Tree
      3. 3.3.3. B+ -Tree(MySQL)
      4. 3.3.4. Hash
      5. 3.3.5. BitMap索引
    4. 3.4. 密集索引和稀疏索引的区别
    5. 3.5. 如何定位并优化慢查询SQL
    6. 3.6. 联合索引的最左匹配原则的成因
    7. 3.7. 索引是建立的越多越好吗
  4. 4. 锁 and 锁 and 锁
    1. 4.1. MyISAM与InnoDB关于锁方面的区别是什么
      1. 4.1.1. 表级锁
      2. 4.1.2. 行级锁
      3. 4.1.3. 共享锁和排他锁
      4. 4.1.4. 乐观锁和悲观锁
      5. 4.1.5. 行级锁一定比表级锁优吗?
      6. 4.1.6. MyISAM和InnoDB各自适合的场景
    2. 4.2. 数据库事务四大特性ACID
      1. 4.2.1. 原子性
      2. 4.2.2. 隔离性
      3. 4.2.3. 一致性
      4. 4.2.4. 持久性
    3. 4.3. 事务隔离级别以及各级别下的并发访问问题
    4. 4.4. InnoDB可重复读隔离级别下如何避免幻读
      1. 4.4.1. 表象
      2. 4.4.2. 内在
    5. 4.5. RC、RR级别下的InnoDB的非阻塞读(快照读)如何实现
  5. 5. 结语