SQL 体系结构和索引

发表于 | 分类于 | | 阅读次数

SQL的体系结构

了解MySql必须牢牢记住其体系结构图，Mysql是由SQL接口，解析器，优化器，缓存，存储引擎组成的。

  1. Connectors指的是不同语言中与SQL的交互

  2. Management Serveices & Utilities： 系统管理和控制工具

  3. Connection Pool: 连接池。管理缓冲用户连接，线程处理等需要缓存的需求

  4. SQL Interface: SQL接口。接受用户的SQL命令，并且返回用户需要查询的结果。比如select from就是调用SQL Interface

  5. Parser: 解析器。SQL命令传递到解析器的时候会被解析器验证和解析。解析器是由Lex和YACC实现的，是一个很长的脚本。 主要功能: 1) 将SQL语句分解成数据结构，并将这个结构传递到后续步骤，以后SQL语句的传递和处理就是基于这个结构; 2) 如果在分解构成中遇到错误，那么就说明这个sql语句是不合理的

  6. Optimizer: 查询优化器。 SQL语句在查询之前会使用查询优化器对查询进行优化。他使用的是选取-投影-联接策略进行查询。用一个例子就可以理解： select uid,name from user where gender = 1; 这个select 查询先根据where 语句进行选取，而不是先将表全部查询出来以后再进行gender过滤这个select查询先根据uid和name进行属性投影，而不是将属性全部取出以后再进行过滤将这两个查询条件联接起来生成最终查询结果

  7. Cache和Buffer： 查询缓存。 如果查询缓存有命中的查询结果，查询语句就可以直接去查询缓存中取数据。这个缓存机制是由一系列小缓存组成的。比如表缓存，记录缓存，key缓存，权限缓存等

  8. Engine ：存储引擎。存储引擎是MySql中具体的与文件打交道的子系统。也是Mysql最具有特色的一个地方。Mysql的存储引擎是插件式的。它根据MySql AB公司提供的文件访问层的一个抽象接口来定制一种文件访问机制（这种访问机制就叫存储引擎）现在有很多种存储引擎，各个存储引擎的优势各不一样，最常用的MyISAM,InnoDB,BDB. MyISAM引擎的查询速度快，有较好的索引优化和数据压缩技术，但是它不支持事务；InnoDB支持事务，并且提供行级的锁定，应用也相当广泛。 Mysql也支持自己定制存储引擎，甚至一个库中不同的表使用不同的存储引擎，这些都是允许的。

SQL索引

B-树

B树是二叉搜索树，可以通过左旋，右旋达到平和，从而提高最坏情况下的搜索时间。B-树是B树的提升版本，是一种多路搜索树，它的定义如下：

  1. 定义任意非叶子结点最多只有M个儿子；且M>2；

  2. 根结点的儿子数为[2, M]；

  3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；

  4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

  5. 非叶子结点的关键字个数=指向儿子的指针个数-1；

  6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

  7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

  8. 所有叶子结点位于同一层；

总结下来他和B树比较大的区别就是每个节点不在只有一个元素，左右两个孩子，而是假设有N个元素，顺序存储，有N+1个孩子，并且所有叶子节点都在同一层

B-树的一个重要的特性就是对节点关键字的查找，等价于在所有元素进行一次二分查找。它和B树在查找方面有相同的时间复杂度，但是树的深度比B树小。（关于B-树的深度，可以通过M来设置）由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并

B+树

B+树是B-树的变体，也是一种多路搜索树，定义基本相同，除了：

  1. 非叶子结点的子树指针与关键字个数相同，例如一个节点有N个元素，那么它就有（最多）N个孩子，并且，节点的每个元素对应一个孩子，还元素还会出现在孩子当中，一直传递下去到叶子节点

  2. 对于查找元素，一定要达到叶子节点才会命中

  3. 由于所有元素都出现在叶子节点当中，也刚好是有序的，因此使用链表将这些节点串联起来

这样看来，B+树的特性很明显，叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；更适合文件索引系统

局部性原理

使用B+树来进行存储，除了深度相比于B树合适外，还和局部性原理与磁盘预读相关，预读的长度一般为页(page)的整倍数，(在许多操作系统中，页得大小通常为4k)数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，(由于节点中有两个数组，所以地址连续)

存储引擎

在 MySQL 中，主要有四种类型的索引，分别为： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引，也是数据库中使用最多最频繁的引擎下面主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式

MyISAM

MyISAM引擎的索引和数据时分开的（在不同文件），叶子节点的data域存放的是数据的地址，因此被称为非聚集索引。索引又分为主索引和辅助索引，它们在结构上完全相同，只是主索引要求key唯一，辅助索引可以重复。

InnoDB

同样适用B+树作为索引结构的InnoDB，有着完全不同的实现。首先，索引文件和数据存储是在同一个文件（主键索引），因此，叫作聚集索引没有指定，会自动选择。因此，叫作聚集索引。InnoDB必须有主键索引，而MyISAM可以没有。InnoDB中，对于辅助索引，同样使用B+树，叶子节点存储的是主键的data域，因此，在辅助索引上搜索数据，需要搜索两次。

关于主键索引的选取，有如下的建议：

  1. 不建议使用过长的字段作为主键，这样做会造成辅助索引变大

  2. 不建议使用非单调递增的字段，因为插入的时候会频繁的分裂和调整，效率低下，应该考虑用自增字段作为主键

MyISAM和innodb对比

目前主流的都是使用innodb，那么它的优势有哪些呢？

  • 它支持事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID compliant))型表

  • 在插入，更新和删除上性能更优。

  • 支持表锁、行锁 行锁大幅度提高了多用户并发操作的新能。但是InnoDB的行锁，只是在WHERE的主键是有效的，非主键的WHERE都会锁全表的

  • 支持外键

  • InnoDB的设计目标是处理大容量数据库系统，它的CPU利用率是其它基于磁盘的关系数据库引擎所不能比的。

MyISAM相对来说处于劣势，但是也有仅有的几个优点：

  • 由于MyISAM的数据是以文件的形式存储，所以在跨平台的数据转移中会很方便。在备份和恢复时可单独针对某个表进行操作

  • SELECT操作更优

  • 支持全文索引