索引可以提高数据查询的效率, 相当于一本书的目录
常见索引模型
数据库的索引模型有很多种, 其中比较常见, 简单的数据结构是哈希, 有序数组和搜索树
哈希表
哈希表是一种 key-value 结构的数据结构, key 为待查找的值, 用一个 hash 函数计算 key 的哈希值, 作为存储位置, value 就放在这个位置, 因为多个 key 可能计算出来 hash 值相同, 即占用相同的位置, 所以 value 可以是一个链表, 里面存着多个值.
image
如图, 根据用户 id 计算 hash 值, 可能 user2,user5 两个用户计算出来的 hash 值相同, 所以他们的数据以链表的形式存在于 value. 如果要获取 user6 的信息, 根据 hash(user6.id) 得出 hash 值为 3, 则在 3 这个 value 中遍历, 获取 user6 的信息. 一个好的 hash 函数计算得到的值应该是非常分散的, 不容易重复, 这样会减少遍历的过程, 增加查询速度.
由于 hash 存储位置的值不是递增的, 而是散列的, 因此插入数据时速度是很快的, 但是如果要查找区间内的值 [user3,user9], 只能挨个从 user3 开始遍历查找, 所以 hash 表这种结构适合于等值查询的场景, 不适合区间查询
有序数组
有序数组对于上述区间查询这一场景有优势, 存储状态如图:
image
按照 id 递增存储在数组中, 如果需要查询某个 id 对应的姓名, 根据二分法时间复杂度为 O(log n), 如果需要查询一个区间的范围, 则开头第一个 user 后一次往后查询即可. 但是如果需要大量插入数据, 数据结构就不适合了, 为了保证 id 的顺序性, 需要往数组中间插入一条, 则该 id 后面的数据一次向后移动, 成本比较高.
以上可见, 有序数组索引只适用于静态存储引擎, 提供查询, 不插入的数据表
N 叉树
二叉树的特点: 每个节点比左儿子大, 比右儿子小. 由结构可知时间复杂度为 O(log n), 为了维持这种结构, 更新的时间复杂度同样是 O(log n). 除了二叉树外还可以有 N 叉树, 对于二叉树来说, 100 万节点的树高 20, 也就是说查找一个数据很有可能要访问 20 个数据块, 这个速度就会很慢. 所以这时候应该使用 N 叉树, N 取决于数据块的大小. N 叉树由于在读写上的性能优点, 以及适配磁盘的访问模式, 已经被广泛的应用在数据库引擎中了
InnoDB 的索引模型
innoDB 使用了 B + 树索引模型, 每个索引都对应着一棵 B + 树.
索引类型分为: 主键索引和费主键索引
主键索引叶子节点存的是整行数据, 也被称为聚簇索引; 非主键索引的叶子节点内容是主键的值, 也被称为二级索引.
也就是说如果通过主键 id 来查找, 则只需要搜索 id 这棵 B + 树
如果使用二级索引来查找, 则先找到该二级索引对应的主键 id 然后再根据 id 索引树在搜索一次, 这个过程叫做回表
如图:
image
select * from table where k = 3
以上 SQL 使用了二级索引 K, 首先搜索索引树, 得到主键 id 的值为 300, 再到主键索引树找到 300 对应的数据, 这一过程叫做回表
因此在应用中减量使用主键索, 可以减少回表过程
索引维护
由于 B + 树的有序性, 所以在插入新数据时需要调整, 维持结构.
在自增主键的情况下, 主键系统自己动获取主键 id, 按顺序在最后插入一个叶子节点, 是追加操作, 不需要移动其他的记录.
使用业务逻辑字段做主键, 则一般不能保证有序插入, 写数据的成本比较高
上文可知, 非主键索引的叶子节点都是主键的值, 如果主键长度越大, 普通索引的叶子节点就越小, 普通索引占用的空间也就越小
从性能和存储空间两方面考虑, 自增主键往往是更合理的选择
本文为极客时间《MySQL 实战 45 讲》的学习笔记, 其中含有部分原文, 如有侵权行为请联系我立刻删除
第一节: 一条 SQL 查询语句的执行过程
来源: http://www.jianshu.com/p/21a17937c1ed