MySQL索引原理

# 1 索引是什么

数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询，更新数据库表中的数据

# 2 索引类型

普通索引 Normal
唯一索引 Unique
全文索引 FullText 解决大文本中like

# 3 索引的数据结构

二叉查找树

顺序依次增大的时候退化为链表，时间复杂度O(n)

平衡二叉树

左右子树的深度差绝对值不能超过1

单个节点存储的信息占据的空间很小，但是分配的空间是16KB，造成资源利用率很低，浪费
树形结构深度很深，会带来很多IO操作，效率急剧下降

磁盘->内存 InnoDB ，操作的最小单位，Page页，一次读取16K ，读取多次，磁盘IO次数过多

多路平衡查找树（B树）

最终在B树中找到索引对应的内存地址，然后去查找对应的数据

加强版多路平衡查找树（B+Tree）

加强版的多路平衡二叉树：叶子节点存储的具体的记录，物理数据和索引都是存储在B+树中

关键字数=dgree
内节点不存储数据
叶子节点有双向指针

B+树和HASH的比较

B+树是一个平衡的多叉树，从根节点到每个叶子节点的高度差值不超过1，而且同层级的节点间有指针相互链接。在B+树上的常规检索，从根节点到叶子节点的搜索效率基本相当，不会出现大幅波动，而且基于索引的顺序扫描时，也可以利用双向指针快速左右移动，效率非常高。因此，B+树索引被广泛应用于数据库、文件系统等场景。简单地说，哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

Hash只适合等值查询，不能范围查找
B+树可以叶子节点有序，链式结构，双向指针可范围查找
Hash效率高，B+数从根节点查找，多次IO
Hash存在Hash碰撞问题

# 4 聚集索引

主键索引
unique key not null
没有索引的情况下，rowid作为聚集索引

# 5 索引优化

（1）联合索引最左匹配必须从第一个字段开始，而且不能中断

（2）覆盖索引 select的字段包含在了用到的索引中，不需要回表

标志：explain extra ：Using index

例子：索引（name，phone）

select * from user where phone = ‘18388461254’   不走索引
select name  from user where phone = ‘18388461254’   会走索引，并且是覆盖索引（优化器处理）
select phone from user where phone = ‘18388461254’   会走索引，并且是覆盖索引（优化器处理）