根据 MySQL索引原理及慢查询优化 整理
索引的目的在于提高查询效率。
通过不断的缩小要查询的数据的范围来筛选出最终想要的结果,同时将随机的事件变成顺序事件。
数据库则复杂得多,不仅需要面对等值查询,还有范围插叙(<, >, between, in)、模糊查询(like)、并集查询(or)等等。 简单的搜索树难以满足复杂的应用场景。
磁盘的IO是非常昂贵的操作。计算机操作系统做了一些优化,当一次IO时,不光读取当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区。每次IO读取的数据我们称之为一页(page)。一页一般为4kb或者8kb。
我们需要的数据结构:每次查找数据时,都要把磁盘IO次数控制在一个很小的数量级,最好是常数数量级。一个高度可控的多路搜索树是否能够满足需求呢?B+树应运而生。
B+树是一种树数据结构,通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入,这与二叉树恰好相反。
真实数据存储于叶子节点,非叶子节点不存储真实数据,只存储指引搜索方向的数据项。
内存查询时间非常短(相比于磁盘的IO)可以忽略不计。真实的情况是3层B+树,可以表示上百万的数据。如果上百万的数据查找只需要三次IO,性能提高将是巨大的。
H=log(M+1)N
。当数据量N一定的情况下,M越大,H越小;而M=磁盘块的大小/数据项的大小
,磁盘块的大小也就是一个数据页的大小,是固定的。如果数据项占用的空间越小,数据项就越多,树的高度就会越低。这就是为什么每个数据项,即索引字段要尽量小。这也是为什么B+树要求把真实数据存储到叶子节点而不是内层节点,一旦放到内层节点,磁盘块的数据项会大幅度下降,导致树增高。当数据项等于1时,将会退化成线性表。COUNT(DISTINCT col)/COUNT(*)
,表示字段的不重复比例,比例越大扫描的表就越少,唯一键的缺乏难度为1。根据使用场景的不同,这个值也很难确定,一般需要join的字段我们都要求是0.1以上。SQL_NO_CACHE
explain
查看执行计划,是否与1预期一致(从锁定记录较少的表开始查询)order by limit
形式的sql语句,让排序的表优先查询任何数据库层面的优化都抵不上应用系统的优化。