MySql教程

数据库原理一---MySQL基本架构与索引

本文主要是介绍数据库原理一---MySQL基本架构与索引,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

MySQL基本架构

Server层包括连接器、查询缓存、分析器、优化器、执行器等,所有跨存储引擎的功能都在这一层实现。
存储引擎层负责数据的存储和提取。其架构模式是插件式的,支持InnoDB(5.5后成为默认存储引擎)、MyISAM、Memory等多个存储引擎。

Server层

  • 连接器
    负责用户登录数据库,进行用户的身份认证,包括校验账户密码,权限等操作。

  • 查询缓存
    客户端与服务端建立连接后,MySQL在执行查询语句时会先查询缓存,校验这条SQL是不是在之前执行过。之前执行过的语句及其结果会以key-value对的形式被直接缓存在内存中。(不建议使用查询缓存,查询缓存的失效非常频繁,只要有对一个表的更新,这个表上所有的查询缓存都会被清空。在MySQL8.0中已删除该功能)

  • 分析器
    分析SQL语句的作用,主要分为以下两步
    1.词法分析,提取关键字
    2.语法分析,判断SQL语句是否正确

  • 优化器
    对SQL语句进行自动优化,对语法分析树的形态进行修改,把语法分析树变为查询树,确定执行方案。

  • 执行器
    执行语句。首先校验用户是否有执行查询的权限,如果有权限,就会去调用引擎的接口,返回接口执行的结果。

存储引擎

常用的存储引擎有以下几种:

  • InnoDB引擎
    Innodb引擎提供了对数据库ACID事务的支持。并且还提供了行级锁和外键的约束。它的设计的目标就是处理大数据容量的数据库系统。
  • MyIASM引擎
    不提供事务的支持,也不支持行级锁和外键。
  • MEMORY引擎
    所有的数据都在内存中,数据的处理速度快,但是安全性不高。

MyISAM与InnoDB的区别

image
关于全文索引:MySQL全文索引在5.7之前只支持英文,5.7之后内置了ngram全文检索插件,用来支持中文分词,对MyISAM和InnoDB引擎都有效。
该处具体到底如何笔者也仍然存在疑问,难以给出准确回答,但是在更多情况下,全文索引我们更倾向于使用elasticSearch等工具实现全文检索。

MySQL索引

索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分),它们包含着对数据表里所有记录的引用指针。
索引是一种数据结构。数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。
更通俗的说,索引就相当于目录。为了方便查找书中的内容,通过对内容建立索引形成目录。索引是一个文件,它是要占据物理空间的。

索引是在存储引擎层实现的,而不是在服务器层实现的,所以不同存储引擎具有不同的索引类型和实现。
在MySQL中使用较多的索引有Hash索引,B+树索引等,而InnoDB存储引擎和MyISAM存储引擎的默认索引实现都为B+树索引。
对于哈希索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景,建议选择BTree索引。

索引的基本原理

索引用来快速地寻找那些具有特定值的记录。如果没有索引,一般来说执行查询时遍历整张表。
索引的原理很简单,就是把无序的数据变成有序的查询

  1. 把创建了索引的列的内容进行排序

  2. 对排序结果生成倒排表

  3. 在倒排表内容上拼上数据地址链

  4. 在查询的时候,先拿到倒排表内容,再取出数据地址链,从而拿到具体数据

B+ Tree

B Tree 指的是 Balance Tree,也就是平衡树。平衡树是一颗查找树,并且所有叶子节点位于同一层。
B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现,它具有 B Tree 的平衡性,并且通过顺序访问指针来提高区间查询的性能。
在 B+ Tree 中,一个节点中的 key 从左到右非递减排列,如果某个指针的左右相邻 key 分别是 keyi 和 keyi+1,且不为 null,则该指针指向节点的所有 key 大于等于 keyi 且小于等于 keyi+1。

B+树的查找、插入、删除
进行查找操作时,首先在根节点进行二分查找,找到一个 key 所在的指针,然后递归地在指针所指向的节点进行查找。直到查找到叶子节点,然后在叶子节点上进行二分查找,找出 key 所对应的 data。

插入删除操作记录会破坏平衡树的平衡性,因此在插入删除操作之后,需要对树进行一个分裂、合并、旋转等操作来维护平衡性。

为什么InnoDB及MyISAM引擎都使用了B+Tree作为索引

B+Tree与红黑树的比较
红黑树等平衡树也可以用来实现索引,但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构,主要有以下两个原因:

  1. 更少的查找次数
    平衡树查找操作的时间复杂度等于树高 h,而树高大致为 O(h)=O(logdN),其中 d 为每个节点的出度。 红黑树的出度为 2,而 B+ Tree 的出度一般都非常大,所以红黑树的树高 h 很明显比 B+ Tree 大非常多,检索的次数也就更多。

  2. 利用计算机预读特性
    为了减少磁盘 I/O,磁盘往往不是严格按需读取,而是每次都会预读。预读过程中,磁盘进行顺序读取,顺序读取不需要进行磁盘寻道,并且只需要很短的旋转时间,因此速度会非常快。
    操作系统一般将内存和磁盘分割成固态大小的块,每一块称为一页,内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小,使得一次 I/O 就能完全载入一个节点,并且可以利用预读特性,相邻的节点也能够被预先载入。

B+Tree与BTree的比较
B树只适合随机检索,而B+树同时支持随机检索和顺序检索

  1. B树只适合随机检索,而B+树同时支持随机检索和顺序检索

  2. B+树空间利用率更高,可减少I/O次数,磁盘读写代价更低。
    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗。
    B+树的内部结点并没有指向关键字具体信息的指针,只是作为索引使用,其内部结点比B树小,盘块能容纳的结点中关键字数量更多,一次性读入内存中可以查找的关键字也就越多,相对的,IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素。

  3. B+树的查询效率更加稳定
    B树搜索有可能会在非叶子结点结束,越靠近根节点的记录查找时间越短,只要找到关键字即可确定记录的存在,其性能等价于在关键字全集内做一次二分查找。
    而在B+树中,顺序检索比较明显,随机检索时,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径长度相同,导致每一个关键字的查询效率相当。

  4. B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。
    B+树的叶子节点使用指针顺序连接在一起,只要遍历叶子节点就可以实现整棵树的遍历,而B树不支持这样的操作。

  5. 增删文件(节点)时,B+树效率更高。
    因为B+树的叶子节点包含所有关键字,并以有序的链表结构存储,这样可很好提高增删效率。

B+树与hash索引

  1. hash索引进行等值查询更快,但是却无法进行范围查询,且等值查询不稳定,性能不可预测
    当某个键值存在且大量重复的时候,发生hash碰撞,此次hash索引效率可能极差
    b+树的查询效率比较稳定,对于所有的查询都是从根节点到叶子节点,且树的高度较低

  2. hash索引不支持使用索引进行排序

  3. hash索引不支持模糊查询以及多列索引的最左前缀匹配

  4. hash索引任何时候都避免不了回表查询,而B+树在符合某些条件的时候可以只通过索引完成查询

B+树对比二叉树
二叉树当数据库的数据量特别大时,其层数也特别大。磁盘IO的次数会由树的高度决定,不使用二叉树是为了压缩树的高度,减少磁盘IO的次数。

InnoDB、MyISAM下索引实现的差异

MyISAM索引实现
MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。
MyISAM会按照数据插入的顺序分配行号,从0开始,然后按照数据插入的顺序存储在磁盘上。因为行是定长的,所以可以从表的开头跳过相应的字节找到需要的行。
MyISAM的索引文件仅仅保存数据记录的行号,然后通过此行号回表查询需要的数据

在MyISAM中,主索引和辅助索引在结构上没有任何区别,只是主索引要求Key是唯一的,而辅助索引的key可以重复。

因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。MyISAM的索引方式索引和数据存放是分开的,非聚集的。

InnoDB索引实现
虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。
聚簇索引的每一个叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。
InnoDB的二级索引的叶子节点存储的不是行号(行指针),而是主键列。这种策略的缺点是二级索引需要两次索引查找,第一次在二级索引中查找主键,第二次在聚簇索引中通过主键查找需要的数据行。

综上,两者都包含非聚簇索引的实现,但是InnoDB引擎支持了聚簇索引。

这篇关于数据库原理一---MySQL基本架构与索引的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!