By

参考

MySQL 索引背后的数据结构及算法原理:

http://blog.codinglabs.org/articles/theory-of-mysql-index.html

MySQL 索引原理及慢查询优化:

https://tech.meituan.com/2014/06/30/mysql-index.html

BTree, B+Tree.

结合磁盘的预取功能，BTree node=页大小(4k),每取 1 个节点就 1 次 I/O. logdN 的查询次数，不会太多 IO.

1 个 Node 的度的计算方式:

dmax=floor(pagesize/(keysize+datasize+pointsize))

MyISAM 引擎

以任何列做 key,

B+Tree 实现.

索引:key 是列的值，value 是数据记录的地址.(行号),索引和数据是分开的

非聚集特性.

辅助索引的 data 域也是数据地址.

InnoDB 引擎

以主键做 key, 叶节点的 data 域就是数据记录本身，而不是 ISam 里的行号,所以叫聚集索引

必须要有主键.

辅助索引存的是 data 域是主键值.因此辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

InnoDB:

InnoDB 中，表数据文件本身就是按 B+Tree 组织的一个索引结构.

所以一定要有主键, 主键不能太长,单调增保证效率.

为何单调好？B+Tree 在插入时，不用分裂过猛.

常见的都是 increment-id(0,1,2,…)

请永远使用一个与业务无关的自增字段作为主键

索引使用策略及优化

单列索引和联合索引: https://blog.csdn.net/Abysscarry/article/details/80792876

联合索引的数据结构: https://blog.csdn.net/weixin_30531261/article/details/79329722

Q:什么样的查询用到联合索引?

(a,b,c)联合索引:

  1. 全列匹配 a=’x’ and b=’x’ and c=’x’ 所有索引列，都出现在(“=”或“IN”中时，叫精确匹配，索引可以被用到.
  2. 最左前缀匹配 a=’x’ and b = ‘x’ 当查询条件精确匹配索引的左边连续一个或几个列时. 但是只能用到一部分，即条件所组成的最左前缀(a)
  3. 查询条件用到了索引中列的精确匹配，但是中间某个条件未提供 a=’x’ and c =’x’ 先找 a=’x’, 再扫描 c=’x’.
  4. 查询条件　没有用索引第１列 b=’x’ 无法使用联合索引

  5. 匹配某列的前缀字符串。 a=’x’ and b like ‘ss%’

  6. 范围查询 where a < ‘dd’ and b = ‘x’
  7. 含有函数表达式不会索引

从最左列开始，遇到范围查询(>、<、between、like)就停止匹配,( 之后的不再索引，靠扫描) (a,b,c,d) 索引，　 a=1 and b =2 and c>3 and d = 10,　 a,b,c 可以用索引，后面的 d 不行 (a,b,d,c) 按上面的查询就 ok 　，因为 c 是在最后.