索引
对任何数据结构来说,在 Read Overhead(读)、Update Overhead(写) 和 Memory or Storage Overhead(存储) 中,同时优化两项时,需要以另一项劣化作为代价
为什么使用索引
- 大大减少了服务器需要扫描的数据量
- 帮助服务器避免排序和临时表
- 将随机io变成顺序io
索引用处
- 快速查找匹配WHERE子句的行
- 从consideration中消除行,如果可以在多个索引之间进行选择,mysql通常会使用找到最少行的索引
- 如果表具有多列索引,则优化器可以使用索引的任何最左前缀来查找行
- 当有表连接的时候,从其他表检索行数据
- 查找特定索引列的min或max值
- 如果排序或分组时在可用索引的最左前缀上完成的,则对表进行排序和分组
- 在某些情况下,可以优化查询以检索值而无需查询数据行
索引使用条件
- 小表全表扫描效率优于索引
- 索引适合中大型表
- 特大型表,建立和维护索引的代价将会随之增长
评价
索引好坏的评价维度
- 访问类型:是否支持范围访问、特定值访问
- 访问时间
- 插入时间
- 删除时间
- 空间开销
一些索引数据结构
- hash(散列索引)
- 可以直接根据key访问
- **但是无法进行范围查询**
- avl(顺序索引)
- 平衡二叉树,左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1
- 支持范围查询
- **插入操作可能需要旋转,效率低**
- b+树(顺序索引)
散列索引
要求全部的索引要能放入内存
- 静态散列
- 动态散列:散列函数、桶大小可以动态改变,性能不随文件增长降低。空间开销小。并且增加了一个中间层,带来微小的性能损失。
位图索引
性别_男= 10010101性别_女= 01101010区_朝阳= 00000100
当要获取朝阳的男的时候,将两个向量相与,结果为1的位置的数据,就是搜索命中的结果
位图操作的高效实现
位图与B+树
采用传统的 B+ 树建立索引,如果数据区分度很低,则B+树效率也不高
顺序索引
- 稠密索引: 每个属性都有一个索引项
- 稀疏索引: 只为某些属性建立索引
多级索引
- 通过将一级索引表放置在内存中加快搜索速度
索引的更新
插入新记录
对于稠密索引:如果该索引值不存在于索引中,则在合适的位置插入索引值,如果存在于索引中,则找到索引值对应的记录链表,在链表尾部追加新记录
对于稀疏索引:在合适的索引值范围内添加新记录
删除记录
对于稠密索引:如果该记录时该索引值的唯一记录,删除即可。否则执行链表的节点删除操作
对于稀疏索引:如果包含了索引值,则删除索引值对应的记录,并调整索引范围
辅助索引
在索引与实际记录之间的一个中间层,也就是非聚簇索引,索引的不是物理位置,而是根据某些列的值建立的一个独立的数据结构
B树
2-3 树是一种特殊的 B- 树
B+树
B-tree减少了定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统
B+树中叶子节点中包含了key和value,非叶子节点中只是包含了key,不包含value
所有叶子节点位于同一层,之间会通过双向指针串联在一起,构成一个双向链表
B+ 树可以让整个树状结构变得更加矮胖,而磁盘的预读特性每次都可以加载一整个节点中全部的键,到内存进行二分查找
如果出现了两条或者多条记录在索引属性上拥有相同的值,解决方法:
- 创建包含原始搜索码和其他额外属性的符合搜索码
- 在B+树节点上使用列表来存储
文件结构
操作
更新操作比较复杂,但是需要较少的 IO 操作
批量加载
如果一次性插入大量数据,在插入前对数据排序再插入到B+树中,可以有效提升性能
同时,如果B+树是空的,还可以使用自底向上的方式来进行构建
查找
首先在根节点进行二分查找,找到一个key的指针,接下来递归地不断向其非叶子节点查找,到了叶子节点,再进行二分查找,找出key所对应的data
修改
查找出要修改节点的位置,由于每个中间节点能容纳的元素是有限的,所以修改之后会进行分裂、合并、旋转
vs红黑树
- 红黑树的出度为2,B树的出度要大很多,所以B树的查找次数更少
- B+ Tree能更好地利用磁盘的预读特性 但操作也会更加复杂
LSM树
log-structured merge tree
Memtable
内存中的数据结构,存储的是近期更新的记录值,可以用各种有序高效的数据结构来实现
Immutable Table
在写入磁盘的过程中,系统很可能仍然在对外工作,所以创建副本,可以很好的地帮助避免读写冲突竞争
SSTable
它要求key是有序的,并且每个段中每个key只能出现一次,查找key时,可以在稀疏索引中通过排序查找里快速找到
为了实现SSTables,需要在内存中维护一个有序的数据结构,每次写入时都会写到内存表,再由系统周期性刷到磁盘,为避免崩溃导致内存的数据还没刷到磁盘丢失,再维护一个日志文件,每进行一个操作就写到日志,以供恢复时使用
需要查找时,就对段逐个倒叙查找,直到找到
MYSQL索引
技术名词
- 回表:使用索引就能完成查询 无需扫描表数据
- 最左匹配:在检索数据时从联合索引的最左边开始匹配,也代表字符串最左N个字符可以走索引
- 索引下推:在“仅能利用最左前缀索的场景”下,在遍历索引时,使用不在最左前缀索引中的其他联合索引字段,过滤会减少遍历索引查出的主键条数,减少回表
分类
- 主键索引
- 唯一索引
- 普通索引
- 全文索引
- 组合索引
B+ Tree索引
- 是大多数 MySQL 存储引擎的默认索引类型
- 除了用于查找,还可以用于排序和分组
- 适用于全键值、键值范围和键前缀查找
存储引擎的实现
MyISAM: B+Tree叶节点的data域存放的是数据记录的地址。在索引检索的时候,首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其 data 域的值,然后以 data 域的值为地址读取相应的数据记录。这被称为“非聚簇索引”
InnoDB: 其数据文件本身就是索引文件。相比MyISAM,索引文件和数据文件是分离的,其表数据文件本身就是按B+Tree组织的一个索引结构,树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。这被称为“聚簇索引(或聚集索引)”。而其余的索引都作为辅助索引,辅助索引的data域存储相应记录主键的值而不是地址,这也是和MyISAM不同的地方。在根据主索引搜索时,直接找到key所在的节点即可取出数据;在根据辅助索引查找时,则需要先取出主键的值,再走一遍主索引。 因此,在设计表的时候,不建议使用过长的字段作为主键,也不建议使用非单调的字段作为主键,这样会造成主索引频繁分裂
哈希索引
- 无法用于排序与分组
- 只支持精确查找,无法用于部分查找和范围查找
- 数据列只能回表查询,无法直接根据索引读取
只有Memory引擎显式支持哈希索引。对于索引比较长的字符序列,哈希索引很好用
InnoDB当某些索引值被使用的非常频繁时,会在B树索引的基础上创建一个哈希索引来提升效率,这个过程是内部且自动的。
为了在InnoDB上模拟出哈希索引,可以考虑使用一个字段存储哈希值,每次查找时对这个哈希值做一个等值比较:
SELECT * FROM tb_url WHERE hash_code = CRC32('http://baidu.com') AND url = 'http://baidu.com';
全文索引
- MyISAM 存储引擎支持(innodb 5.6后支持)
- 用于查找文本中的关键词
- 查找条件使用 MATCH AGAINST
- 使用倒排索引
空间数据索引
空间数据索引(R-Tree),可以用于地理数据存储
索引匹配方式
- 全值匹配 全值匹配指的是和索引中的所有列进行匹配
explain select * from staffs where name = 'July' and age = '23' and pos = 'dev'
- 匹配最左前缀 只匹配前面的几列
explain select * from staffs where name = 'July' and age = '23';explain select * from staffs where name = 'July';
- 匹配列前缀 可以匹配某一列的值的开头部分
explain select * from staffs where name like 'J%'; -- 可以用索引explain select * from staffs where name like '%y'; -- 用不到索引
- 匹配范围值 可以查找某一个范围的数据
explain select * from staffs where name > 'Mary';
- 精确匹配某一列并范围匹配另外一列 可以查询第一列的全部和第二列的部分
explain select * from staffs where name = 'July' and age > 25;
- 只访问索引的查询 查询的时候只需要访问索引,不需要访问数据行,本质上就是覆盖索引
explain select name,age,pos from staffs where name = 'July' and age = 25 and pos = 'dev';
组合索引
当包含多个列作为索引,需要注意的是正确的顺序依赖于该索引的查询,同时需要考虑如何更好的满足排序和分组的需要
聚簇索引与非聚簇索引
一种数据存储方式。
聚簇索引:不是单独的索引类型,而是一种数据存储方式,指的是数据行跟相邻的键值紧凑的存储在一起
在InnoDB中,默认会选择主键来做举出索引,若没有主键,会生成一个隐藏的主键,主键最好使用自增的数值类型,这样在插入效率及空间占用都会最优
非聚簇索引:数据文件跟索引文件分开存放
使用索引排序
EXPLAIN的type为index时 代表使用索引扫描做排序
只有当ORDER BY子句的列都是索引且排序方向一致时,才会使用索引排序
覆盖索引
如果一个索引包含所有需要查询的字段的值,称之为覆盖索引,当需要的数据被索引覆盖时,就不必回表查询。
只使用索引可以减少数据读取量,同时由于索引是顺序存储的,相比直接读取数据,拥有较好的IO性能。
MySQL中只能使用B树索引做覆盖索引
EXPLAIN SELECT store_id,film_id FROM inventory; -- Extra:Using index 代表可以做覆盖索引
压缩索引
MyISAM会使用前缀压缩的方式将降低索引空间占用,从而使更多的索引可以放入内存。但代价是牺牲了CPU的运算时间。
MyISAM和InnoDB对B+Tree的使用
MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录
myisam
innodb
索引优化
如果表很大,索引反而会造成性能下降
如果有索引,增删改都会变慢
少量查询仍然很快
但是并发大的时候会受到硬盘带宽影响
独立的列
进行查询时,索引列不能是表达式的一部分,也不能是函数的参数
SELECT a FROM B WHERE a+3 = 6; -- 无法用到索引
像字符串跟数值比较的隐式类型转换、字段运算、字段是函数的参数、字符集不同等,本质上都是对字段做了转换操作,可能会破坏索引值的有序性,因此优化器就决定放弃走索引树的搜索,但还是会遍历索引
前缀索引
可以选择开始的部分字符串来进行索引,索引的列的不重复值数量/总数量=索引的选择性 选择性越高 查询效率越好
前缀索引占用的空间会比较少,但同时会增加扫描次数,为了达到索引空间与查询性能的平衡,需要统计数据整体前缀的区分度,选取一个折中的前缀索引长度
BLOB、TEXT 和 VARCHAR 类型的列,必须使用前缀索引
前缀索引无法进行ORDER BY 或者GEOUP BY,也无法覆盖扫描,需要再回表查询
有时候又需要后缀索引,为了达成这个目的,一种hack的方式是把字符串反转后进行存储
多列索引
多个列作为条件进行查询时,使用多列索引比使用多个单列索引性能更好
MySQL会进行一项称为索引合并的策略,一定程度上可以使用多个单列索引来定位指定的行
组合索引
当一个索引不止一个列时,只有当最左索引(索引的第一个列)出现时,才会走索引查询
索引列的顺序
在不考虑排序和分组时,让选择性最强的索引列放在前面
一个列比另外一个列更越能确定一条数据,则前者选择性更强。但还有一种情况就是数据分布不均匀,也有可能造成索引的效果非常差
覆盖索引
索引包含所有需要查询的字段的值
- 只读取索引能大大减少数据访问量
- 一些存储引擎只缓存索引
索引扫描
使用EXPLAIN时 ,type为index,代表使用了索引扫描来进行排序
使用索引扫描来排序
只有当索引的列顺序和order by子句的顺序完全一致,并且所有列的排序方式都一样时,mysql才能够使用索引来对结果进行排序
冗余索引
大多数情况下应尽量扩展已有的索引而非创建新索引,索引越多,更新的时候越慢。
但有时候为了兼容多个查询情况,为创建冗余索引来提升性能
细节
union all,in,or都能够使用索引,但是推荐使用in
范围列可以用到索引 范围条件是:<、<=、>、>=、between 范围列可以用到索引,但是范围列后面的列无法用到索引,索引最多用于一个范围列
强制类型转换会全表扫描
更新十分频繁,数据区分度不高的字段上不宜建立索引 更新会变更B+树,更新频繁的字段建议索引会大大降低数据库性能 区分不大的属性,建立索引是没有意义的,不能有效的过滤数据
创建索引的列,不允许为null,可能会得到不符合预期的结果
当需要进行表连接的时候,最好不要超过三张表,因为需要join的字段,数据类型必须一致
- 三种join实现方式
能使用limit的时候尽量使用limit
单表索引建议控制在5个以内
单索引字段数不允许超过5个(组合索引)
一些错误概念:
- 索引越多越好
- 过早优化
索引监控
show status like 'Handler_read%';
- Handler_read_first:读取索引第一个条目的次数
- Handler_read_key:通过index获取数据的次数
- Handler_read_last:读取索引最后一个条目的次数
- Handler_read_next:通过索引读取下一条数据的次数
- Handler_read_prev:通过索引读取上一条数据的次数
- Handler_read_rnd:从固定位置读取数据的次数
- Handler_read_rnd_next:从数据节点读取下一条数据的次数
维护索引和表
CHECK TABLE 命令可以找出大多数表和索引的错误,使用REPAIR TABLE来修复损坏的表
使用ANALYZE TABLE 重新生成表的统计信息
使用OPTIMIZE TABLE来整理碎片,对于不支持的存储引擎,执行
ALTER TABLE table_name ENGINE=old_engine