MySQL的索引类型
从数据结构角度
- B+树索引(O(nlogn))
- hash索引：
- 仅仅能够满足”=”,”IN”和”<=>”查询，不能使用范围查询, 无法通过操作索引来排序
- 检索效率最高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引
- 不能避免全表扫描,当存在大量相同hash值得时候，hash索引的效率会变低
- FULLTEXT索引:支持full-text的字段只有char、varchar、text数据类型, 主要是用来代替like “%*%”效率低下的问题
从物理存储角度
- 聚簇索引（clustered index）
- 非聚簇索引（non-clustered index）
从逻辑角度
- 主键索引(PRIMARY)：主键索引是一种特殊的唯一索引，不允许有空值
- 普通索引(NORMAL)或单列索引
- 多列索引（复合索引)：复合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用复合索引时遵循最左前缀集合
- 唯一索引或者非唯一索引
索引添加
1 | ALTER TABLE `tab1` ADD INDEX `idx_index_name` USING BTREE (`field1`, `field2`) comment ''; |
平衡二叉树（Balanced Binary Tree)
性质
- 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
- 并且左右两个子树都是一棵平衡二叉树。
常用算法
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等
BTree,B+Tree
B树(即二叉搜索树)
- 所有非叶子结点至多拥有两个儿子（Left和Right）
- 所有结点存储一个关键字；
- 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
B+树
- 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字自小而大顺序链接
- 不可能在非叶子结点命中；
- 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
- 更适合文件索引系统；
总结
- B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
- B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；
- 所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
- B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
- B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
B+Tree索引实现原理
B+树概念
B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接。
B+树示意图：
InnoDB数据页结构
组成部分：File Header(文件头)、Page Header(页头)、Infimun + Supremum Records、User Records(用户记录，即行记录)、Free Space(空闲空间)、Page Directory(页目录)、File Trailer(文件结尾信息)
页是InnoDB存储引擎管理数据库的最小磁盘单位,InnoDB中的页大小为16KB，且不可以更改。
叶子节点(页与页之间)是双向链表串起来的，头连上一页的尾，尾连下一页的头
每个数据页中有两个虚拟的行记录，用来限定记录的边界。(行记录是记录在页中的，同时是在页内行记录之间也是双向链表链接的)
页目录(Page Directory)通过顺序排放的记录指针(也叫槽)存放了记录的相对位置，通过这些槽找到具体的数据位置
页目录中存放了记录的相对位置，有些时候这些记录指针称为Slots（槽）或者目录槽，与其他数据库不同的是，InnoDB并不是每个记录拥有一个槽，InnoDB中的槽是一个稀疏目录，即一个槽中可能属于多个记录，最少属于4个目录，最多属于8个目录。槽中记录按照键顺序存放，这样可以利用二叉查找迅速找到记录的指针。但是由于InnoDB中的Slots是稀疏目录，二叉查找的结果只是一个粗略的结果，所以InnoDB必须通过recorder header中的next_record来继续查找相关记录。同时slots很好的解释了recorder header中的n_owned值的含义，即还有多少记录需要查找，因为这些记录并不包括在slots中
查询B+树索引的流程
首先通过B+树索引找到叶节点，再找到对应的数据页，然后将数据页加载到内存中，通过二分查找Page Directory中的槽，查找出一个粗略的目录，然后根据槽的指针指向链表中的行记录，之后在链表中依次查找。
注意：
B+树索引不能找到具体的一条记录，而是只能找到对应的页。把页从磁盘装入到内存中，再通过Page Directory进行二分查找，同时此二分查找也可能找不到具体的行记录（有可能会找到），只是能找到一个接近的链表中的点，再从此点开始遍历链表进行查找。
聚簇索引/非聚簇索引
区别：
- 聚簇索引一般是为主键索引，一张表只能有一个聚簇索引，B+树的叶子节点存储了行数据和主键。
- 非聚簇索引可以有多个，叶节点除了包含关键字键值外还包含聚集索引的主键
聚集索引
聚集索引是按每张表的主键构造的一颗B+树，并且叶节点中存放着整张表的行记录数据，因此也让聚集索引的节点成为数据页，这个特性决定了索引组织表中数据也是索引的一部分。由于实际的数据页只能按照一颗B+树进行排序，所以每张表只能拥有一个聚集索引。查询优化器非常倾向于采用聚集索引，因为其直接存储行数据，所以主键的排序查询和范围查找速度非常快。
不是物理上的连续，而是逻辑上的，不过在刚开始时数据是顺序插入的所以是物理上的连续，随着数据增删，物理上不再连续。
辅助索引
辅助索引页级别不包含行的全部数据。叶节点除了包含键值以外，每个叶级别中的索引行中还包含了一个书签，该书签用来告诉InnoDB哪里可以找到与索引相对应的行数据。其中存的就是聚集索引的键。
辅助索引的存在并不影响数据在聚集索引的结构组织。InnoDB会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后通过主键索引找到一个完整的行记录。当然如果只是需要辅助索引的值和主键索引的值，那么只需要查找辅助索引就可以查询出索要的数据，就不用再去查主键索引了。
什么是一级索引、二级索引及生成场景
每个InnoDB表具有一个特殊的索引称为聚簇索引（也叫聚集索引，聚类索引，簇集索引）。
- 如果表上定义有主键，该主键索引就是聚簇索引。
- 如果未定义主键，MySQL取第一个唯一索引（unique）而且只含非空列（NOT NULL）作为主键，InnoDB使用它作为聚簇索引。
- 如果没有这样的列，InnoDB就自己产生一个这样的ID值，它有六个字节，而且是隐藏的，使其作为聚簇索引。
表中的聚簇索引（clustered index ）就是一级索引，除此之外，表上的其他非聚簇索引都是二级索引，又叫辅助索引（secondary indexes）
MyISAM和InnoDB索引实现
原始数据如图：
MyISAM引擎索引实现方式
索引实现原理
是按列值与行号来组织索引的。它的叶子节点中保存的实际上是指向存放数据的物理块的指针。从MYISAM存储的物理文件我们能看出，MYISAM引擎的索引文件（.MYI）和数据文件(.MYD)是相互独立的。
主键索引与二级索引
MyISAM的主键索引和二级索引叶子节点存放的都是：列值与行号的组合，叶子节点中保存的是数据的物理地址
MYISAM的主键索引和二级索引没有任何区别：主键索引仅仅只是一个叫做PRIMARY的唯一、非空的索引，且MYISAM引擎中可以不设主键。
InnoDB引擎索引实现方式
1. 聚簇索引(一级索引)
聚簇索引中的每个叶子节点包含主键值、事务ID、回滚指针(rollback pointer用于事务和MVCC）和余下的列(如col2)，如下图：
2. 非聚簇索引(二级索引)
InnoDB的二级索引与主键索引有很大的不同，InnoDB的的二级索引的叶子节点存放的是：KEY字段加主键值，而不是行指针(row pointers)，如下图
二级索引查询步骤：先查到主键值，然后InnoDB再根据查到的主键值通过主键索引找到对应的数据块。
INNODB和MYISAM的主键索引与二级索引的对比
如图：
参考资料：高性能MYSQL
参考
平衡树
BTree,B-Tree,B+Tree,B*Tree都是什么
MySQL有哪些索引类型 ?
mysql索引类型 normal, unique, full text
MySQL_innoDB索引底层原理详解
MYSQL性能调优: 对聚簇索引和非聚簇索引的认识
面试知识点6：MySQL中InnoDB的一级索引、二级索引