树中查找的效率与二叉树的高度成反比,即高度越低,查找效率越高,红黑树虽然也属于平衡树,但是与B+树相比,存储相同的数据,高度更低,因此查找效率更高。

MySQL索引机制及查询优化

索引

B树

B树属于多叉树,每个节点由关键字和指向孩子节点的指针组成,如下图:
image.png
每一层的节点从左至右依次递增,查找的时候根据二分查找,逐渐找到待查找结点的范围。

B+树

B+树也属于B树,是对B树的一种改进,在B+树中所有的关键字数据都在叶子节点,非叶子结点只保存关键字记录的指针。结构如图:
image.png
从上图中可以看出在B+中叶子节点包含了所有的数据并通过指针相连,顺序处于递增;

B+树与红黑树的比较

  • 查找效率更高
    • 因为树中查找的效率与二叉树的高度成反比,即高度越低,查找效率越高,红黑树虽然也属于平衡树,但是与B+树相比,存储相同的数据,高度更低,因此查找效率更高。
  • 可以利用磁盘的预读特性
    • 在计算机中为了减少磁盘的I/O次数,磁盘往往都会对待读的数据进行预读,在预读的过程,数据顺序读取,不需要进行磁盘寻道,并且只需要很短的磁盘旋转时间,速度会加快,提高了读取的效率。
    • 操作系统会将内存和磁盘分成固定大小的块,每一块称之为一页,内存和磁盘的通信就会以页为单位进行交换数据,数据库系统借助这种特性,将索引的一个结点的大小设置为页的大小,这样每次I/O都会完整的载入一个结点,并且利用预读的特性 ,相邻的结点也被预先载入;

MySQL索引

MySQL的索引机制是使用了B+tree,B+树是基于B树和叶子节点的顺序访问指针来实现的;B树是一种平衡树,所有的叶子节点位于同一层。在MySQL中索引机制不仅用在了查找,也用于了排序和分组。

聚簇索引

InnoDB的B+树采用了主索引和辅助索引,主索引的叶子结点data域记录着完整的数据记录,这种索引方式被称为聚簇索引。一个表只能有一个聚簇索引。

辅助索引

辅助索引的叶子结点会记录data域的主键值,在使用辅助索引的时候会先查找到主键值,然后再到主索引中进行查找。

哈希索引

哈希索引可以用O(1)的时间复杂度进行查找,但是具有无序性,因此无法用于排序分组,也不能用于范围查找。在InnoDB存储引擎中有一个自适应哈希索引,它的使用是当在MySQL中某个索引值使用频繁的时候,可以在B+TRee的索引上再建立一个哈希索引,这样这个索引就有了哈希索引的特性。

全文索引

全文索引是存储引擎MyISAM的特性,它的作用是查找文本的关键词,并不是直接相等;
查找条件使用match against,并不是where;
InnoDB存储引擎再MySQL5.6.4版本中也支持了全文索引;

空间数据索引

MyISAM存储引擎也支持空间数据索引(R-tree),可以用于地理数据的存储。

索引的优化

  • 使用索引列进行查询的时候,索引列不可参与运算或者函数运算 ,否则索引失效,如:
1
select age from student where age + 1 = 6
  • 当使用like的时候’%aaa%’,不使用索引,但是’aaa%’可以;
  • 当需要使用多个列进行查询的时候,使用多列索引的性能会更好;
  • 将选择性最强的 索引放在最前面,选择性强度主要是不重复的 索引值和记录的总数的比值,最大值为1,即,每个记录都有唯一的索引,查找效率最高;
1
2
3
4
5
select  count(distinct  stu_id)/count(*) as stuid,
count(distinct teach_id)/count(*) as teachid from school;
# 结果输出
stuid:0.0003
teachid:0.444

对于上述结果,应该将 teach_id放在多列索引的前面;

  • 当操作BLOB、TXT、VARCHAR类型的列是指索引最开始的部分字符;前缀 的选择根据选择性决定;

  • 索引如果包括所有需要查询的字段的值,则使用覆盖索引;

    • 一般覆盖索引指的是一个查询语句只用 辅助索引就可以查询到所有的 数据 ,这样就无序再去查聚簇索引 ;

      索引的优点总结

  • 减少了扫描全部数据就可以查找到精确的数据 ;

  • 索引自带的排序和分组提高查找效率 ;

  • 利用 磁盘预读,将I/O读取的随机操作,间接的变成了顺序预读;

查询的优化

在MySQL查询语句中可以使用 Explain+select语句,根据这个结果优化查询的语句;结果中包含可以查询的类型、索引、扫描的行数。

查询语句的优化

  • 返回需要的列,尽量避免select *;
  • 使用Limit限制返回需要的行;
  • 使用缓存进行查询;
  • 创建索引,使用索引查询;
  • 查询的语句返回的内容过多的时候,可以分解查询
  • 可以将关联多个表的查询:如连接查询分开成单个表的操作,可以在应用程序中进行关联。
    • 可以避免缓存的失效,否则如果一旦一个表发生了变化,那么关联这个表的所有缓存都会失效;
    • 减少锁的竞争;