数据库索引
什么是数据库的索引, 图书馆的书就类似我们数据库表中的数据, 楼层索引排, 书架分类标识, 索书号就类似我们查找数据的索引.索引也可以理解为一本书的目录 .而当用户通过目录查询某个章节的某个知识点, ,所以可以有效的提高数据库系统的整体性能.那我们常用的数据库的索引底层的数据结构是什么样的.要了解数据库索引的底层原理,我们就得先了解一种叫树的数据结构, 而树中很经典的一种数据结构就是二叉树.
评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘IO操作次数的渐进负杂度.
换句话说, 索引的结构组织要尽量减少查找过程中磁盘IO的存取次数.
二叉树(binary search trees)
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆.
b-树
其实从算法逻辑上来讲, 二叉查找树的查找速度和比较次数都是最小的,但是, 我们不得不考虑一个现实问题:磁盘IO,数据库索引是存储在磁盘上的, 当数据量比较大的时候, 索引的大小可能有几个G甚至更多.当我们利用索引查询的时候, 能把整个索引全部加载到内存吗, 显然不可能, 能做的只有逐一加载每一个磁盘页, 这里的磁盘页对应着索引树的节点,
所以,最坏情况下, 磁盘IO次数等于索引树的高度,没错,既然如此,为了减少磁盘IO的次数, 我们就需要把原本”廋高”的树结构变的矮胖.这就是b-树的特征之一.b树是一种多路的平衡查找树, 他的每一个节点最多包含k个孩子,k被称为b树的阶.k的大小取决于磁盘页的大小.
b-树在查询中的比较次数其实不比二叉查找树少, 尤其当单一节点中的元素量很多时,可是相比磁盘IO的速度, 内存中的比较耗时几乎可以忽略.所以只要树的高度足够低, IO次数就足够少,就可以提升查找性能.相比之下节点内部元素多一些也没有关系,仅仅是多了几次内存交互,只要不超过磁盘页的大小即可,这就是b-树的优势之一.b-树的一大优势就是自平衡.
b-树主要应用于文件系统以及部分数据库索引, 比如著名的非关系型数据库Mongodb.而大部分关系型数据库,比如mysql, 则使用b+树作为索引.
b+树
b+ 树是基于b-树的一种变体,有着比b-树更高的查询性能.
平衡二叉树
平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构
基础架构:一条sql查询语句是如何执行的.
1 | mysql> select * from T where ID=10 |
大体来说, mysql可以分为server层和存储引擎层两部分.
server层包括连接器, 查询缓存, 分析器, 优化器, 执行器等, 涵盖mysql的大多数核心服务功能, 以及所有的内置函数(如日期, 时间, 数学和加密函数等), 所有跨存储引擎的功能都在这一层实现, 比如存储过程,触发器吗视图等.
而存储引擎层负责数据的存储和提取 .其架构模式是插件式的, 支持innodb, mylsam, memory等多个存储引擎.现在常用的存储引擎是innodb, 它从mysql 5.5.5 版本开始成为了默认存储引擎.
也就是说, 你执行create table 建表的时候, 如果不指定引擎类型, 默认使用的就是innodb.不过你也可以通过指定存储引擎的类型来选择别的引擎, 比如在crate table语句中使用engine=memory, 来指定使用内存引擎创建表.不同存储引擎的表数据存取方式不同, 支持的功能也不同.
从图中不难看出, 不同的存储引擎共用一个server层, 也就是从连接器到执行器的部分.
连接器
第一步,你会先连接到这个数据库上, 这时候接待你的就是数据库, 连接器负责跟客户端建立连接吗获取权限, 维持和管理连接.连接命令一般这么写
1 | mysql -h$ip -P$port -u$user -p |
输完命令之后, 你就需要在交互对话里面输入密码.虽然密码也可以直接在-p后面写在命令行中, 但这样可能会导致你的密码泄露.如果你连的是生产服务器, 强烈建议你不要这么做.
连接命令中的mysql是客户端工具, 用来跟服务端建立连接.在完成经典的TCP握手后, 连接器就开始认证你的身份, 这个时候用的就是你输入的用户名和密码.
如果用户名或密码不对, 你就会收到一个”Access denied for user”的错误,然后客户端程序结束执行.
如果用户名密码认证通过, 连接器会权限表里面查出你拥有的权限.之后,这个连接里面的权限判断逻辑, 都将会依赖于此时读到的权限.
这就意味着, 一个用户成功建立连接后, 即使你用管理员账号对这个用户的权限做了修改, 也不会影响已经连接的权限.修改完成后, 只有再新建的连接才会使用新的权限设置.
连接完成后, 如果你没有后续的动作, 这个连接就处于空闲状态, 你可以在show processlist命令中看到它.文本中这个图是show processlist的结果, 其中的command列显示为”sleep”的这一行, 就表示现在系统里面有一个空闲连接.
客户端如果太长时间没动静, 连接器就会自动将它断开.这个时间是由wait_timeout控制的.默认值是8小时.
如果在连接被断开之后, 客户端再次发送请求的话, 就会收到一个错误提醒: Lost connection to mysql server during query/这时候如果你要继续, 就需要重连, 然后再执行请求了.
数据库里面, 长连接是指连接成功后, 如果客户端持续有请求, 则一直使用同一个连接.短连接则是指每次执行完很少的几次查询就断开连接, 下次查询在重新建立一个.
建立连接的过程通常是比较复杂的, 所以我建议你在使用中药尽量减少连接的动作,也就是尽量长连接.
但是全部使用长连接后, 你可能会发现, 有些时候mysql占用内存涨的特别空间快, 这是因为mysql在执行过程中临时使用的内存是管理在连接对象里面的. 这些资源会在连接断开的时候才会释放. 所以如果长连接累积下来, 可能导致内存占用太大.被系统强行杀掉(oom), 从现象看就是mysql异常重启.
怎么解决这个问题,你可以考虑以下两种方案.
- 定期断开长连接.使用一段时间, 或者程序里面判断执行过一个占用内存的大查询后, 断开连接, 之后在查询再重连.
- 如果你用的是mysql 5.7 或更新版本,可以在每次执行一个比较大的操作后, 通过执行mysql_reset_connection来重新初始化连接资源.这个过程不需要重连做权限验证, 但是会将连接恢复到刚刚创建完时的状态.
查询缓存
连接建立完成后, 你就可以执行select语句了.执行逻辑就会来到第二步: 查询缓存.mysql拿到一个查询请求后, 会先到查询缓存看看, 之前是不是执行过这条语句.之前执行过的这条语句及其结果可能会以key-value对的形式, 被直接缓存在内存中.key是查询的语句, value是查询的结果.如果你的查询能够直接在这个缓存中找到key, 那么这个value就会被直接返回给客户端.
如果语句不在查询缓存中, 就会继续后面的执行阶段.执行完成后, 执行结果会被存入查询缓存.你可以看到,如果查询命中缓存,mysql不需要执行后面的复杂操作,就可以直接返回结果, 这个效率会很高.
但是大多数情况下我会建议你不要使用查询缓存, 为什么呢?因为查询缓存往往弊大于利.
查询缓存的实效非常频繁, 只有对一个表的更新, 这个表上所有的查询缓存都会被清空.因此很可能你费劲地把结果存起来, 还没使用呢, 就被一个更新全清空了.对于更新压力大的数据库来说, 查询缓存的命中率会非常低, 除非你的业务就是有一张静态表, 很长时间才会更新一次, 比如, 一个系统配置表, 那这张表上的查询才适合查询缓存.
好在mysql也提供了这种”按需使用”的方式.你可以将参数query_cache-type设置成DEMAND, 这样对于默认的sql语句都不使用查询缓存.而对于你确定要使用查询缓存的语句, 可以用sql_cache显示指定, 像下面这个语句一样:1
mysql>select sql_cache * from T where ID=10;
需要注意的是, mysql 8.0 版本直接将查询缓存的整个功能删掉了, 也就是说8.0开始彻底没有这个功能.
分析器
如果没有命中查询缓存, 就要开始真正执行语句了.首先, mysql需要知道你要做什么, 因此需要对sql语句做解析.
分析器先做”语法分析”. 你输入的是有多个字符串和空格组成的一条sql语句, mysql需要识别里面的字符串分别是什么, 代表什么.
mysql从你输入的”select”这个关键字识别出来, 这是一个查询语句, 他也是要把字符串”T”识别成”表名 T”, 把字符串”ID”识别成”列 ID”.
做完了这些识别以后, 就要做”语法分析”.根据词法分析的结果, 语法分析器会根据语法规则, 判断你输入的这个sql语句是否满足mysql语法.
如果你的语句不对, 就会收到”You have an error in your SQL syntax”的错误提醒, 比如下面这个语句select少打了开头的字母”s”.
一般语法错误会提示第一个出现错误的位置, 所以你要关注的是紧接”user near”的内容.
优化器
经过了分析器, mysql就知道你要做什么了.在开始执行之前, 还要先经过优化器的处理.
执行器
mysql通过分析器知道了你要做什么, 通过优化器知道了怎么做, 于是就进入了执行器阶段, 开始执行语句.
开始执行的时候, 要先判断一个你对这个表T有没有执行查询的权限, 如果没有, 就会返回没有权限的错误, 如下所示.
如果有权限, 就打开表继续执行, 打开表, 执行器就会根据表的引擎定义, 去使用这个引擎提供的接口.
