索引
介绍
索引是一种数据结构，数据库存储数据使用该结构，可以帮助我们高速的查询数据
索引类似字典开头的目录，可以帮我们快速的定位到某些数据
数据结构
- 数组
- 链表
- 二叉树
- 红黑树
- 哈希表
- B树
以上都是待选的用于作为索引的数据结构，
在考虑一个数据结构是否适合当索引的时候需要从以下两个方面来考察：
- 查询单个值
- 查询范围值
数组
在使用数组存储的时候，由于没有大小顺序的要求，所以不管查询单个值，还是查询范围值，都需要遍历数组
链表
与数组一样，在查询的时候需要遍历整个链表
二叉树
- 查询单个值：不需要遍历，只需要根据根节点向下查找即可
- 查询范围值：需要查询目标值和父子节点，需要一层一层的反复来回查找
红黑树
与二叉树没有本质的区别，使用二叉树和红黑树主要的缺点是：
- 在查询范围值的时候需要来回反复查找节点的父子节点
- 如果数据量比较大，会导致树的高度特别高，使查找的效率明显降低
Hash表
- 查询单个值：通过对Hash表取余就能得到该值所在的位置，但会存在哈希冲突的问题，整体来说速度比较快
- 查询范围值：需要遍历整个hash表，因为是通过取余来散列的，所以不能保证数值是连续的
Hash表只适合当做哈希索引，只在MySQL内部使用，用于明确的只查询单个值的情况
B树
是一种多路平衡查找树，一个节点可以存储多个值，这样使得树的高度降低
- 查找单个值：比较方便，只需要根据父节点向下寻找即可
- 查找范围值：与二叉树和红黑树一样，需要在父子节点之间来回反复查找
B+树
数据库中索引的真正的数据结构，在B树的基础上做了以下几点优化：
- 在叶子节点之间维护一个指针，指向下一个叶子节点
- 所有的非叶子节点都在叶子节点中维护一个冗余的数据
- 非叶子节点不存储data只存储key
- 叶子节点存储一份完整的key和data
由于磁盘预读的特点，一次磁盘的IO一般读取的是4k，B+树节点的大小设置为4k，所以非叶子节点中只存储Key就能存储更多的数据，降低树的层数，有利于提高查找效率
索引的实现
- 连接器：负责连接的管理和权限的验证
- 解析器：主要是词法解析和语法解析
- 词法解析：主要是看一下关键字等等是否存在错误
- 语法解析：检查一下是否符合语法标准
- 优化器：主要是负责SQL语句的优化常见的优化有：
- 索引优化：选择那个索引去查询
- 连接的顺序优化：假如当存在多表的连接的时候，连接的先后顺序会影响到查询的性能，MySQL的优化器会选出效率最高的连接的顺序
- 执行器：主要去调用存储引擎的接口，查询数据
- 存储引擎：负责数据的存储与管理
MyISAM
非聚集索引，数据文件和索引文件分开，通常需要三个文件
- 主键索引
根据主键这一列建立的索引，拿主键的值建立一个B+树，节点中的key是主键，data是数据对应地址值 - 非主键索引
实质就是根据其他列建立的B+树，存储的key依然是索引列的值，data是数据对应的地址值 .frm表结构定义文件.MYD数据文件.MYI索引文件
InnoDB
是Mysql默认的存储引擎
- 主键索引
根据主键的值建立的B+树，是聚集索引：数据文件和索引文件放在一起，通常只需要两个文件
数据依赖于主键索引树来存储，所以如果在建表的时候没有指定主键，会提供一个默认的主键
key存储的是主键值，data存储的就是主键值对应的这一行的其他的数据 - 非主键索引
根据其他列建立的索引树，key存储的是该列的值，data存储的是这一列对应的主键值
实质上还是依赖于主键来存储数据，所以这也是一种非聚集索引
MyISAM和InnoDB的区别
- InnoDB支持事务，MyISAM不支持事务
由于MyISAM不支持事务，所以一般只有查询需求的表才适用，例如历史记录
InnoDB中的每条SQL语句都会自动封装成事务，自动提交，所以会影响效率
如果需要手动提交事务就需要使用connection.setAutoCommit(false) - InnoDB支持外键，MyISAM不支持外键
- InnoDB中的主键索引是聚集索引，MyISAM中的都是非聚集索引
- InnoDB中的表文件是2个，MyISAM中的是3个
- InnoDB不会保存表的行数，MyISAM会保存表的行数
- InnoDB必须有主键，MyISAM可以没有
- InnoDB支持表锁和行锁，但MyISAM只支持表锁
- 表锁：对整张表加锁
- 行锁：只对行进行加锁
锁的粒度越小，效率就越高
索引的语法
-- 创建表的时候指定索引 create table stu( id int primary key auto_increment, name varchar(20), age int, -- 指定索引的语法 index index_name(name) using btree ) engine = InnoDB character utf8; -- 默认使用的是InnoDB引擎，且默认会根据主键来建立索引 -- unique也是索引列，如果一个字段加上了unique，那么该列也是索引列 -- 添加索引 alter table tableName add[unique] index indexName(columnName); -- 删除索引 alter table tableName drop index idx_name; -- 查询索引 show index from tableName;
一个表中最好维护5个索引
面试题
1.索引采用的是什么数据结构？为什么采用这种数据结构
采用的是B+树，因为B+效率高。然后说一下B+树对比其他的几个数据结构的优点
2.数据库为什么要定义主键，并且在MySQL中使用推荐使用主键自增的策略？
因为InnoDB会默认使用主键来建立索引，如果不定义主键的话会维护一个隐藏的列当做主键
如果没有使用自增的策略，插入的主键数值无法控制，时大时小会影响插入的效率，因为B+树在执行插入操作的时候会进行结构上的转换，如果数据时大时小会大幅度的改变B+树的结构
3.InnoDB和MyISAM有什么区别？什么情况下使用MyISAM？
- MyISAM不支持事务
- MyISAM会保存整个表的行数
- 在只有查询需求的时候使用MyISAM
4.什么是回表？如何避免回表？
在InnoDB表中查询的时候，如果是根据非主键索引树来查询的话，首先会查找到主键的值，然后再根据主键的值在主键的索引树中查找，这样就需要多次查找，这就是回表的现象
在业务允许的范围内，避免使用select *，即尽量只查出我们所需要的数值
建立联合索引
5.索引性能这么好，是不是一个表建立的索引越多越好？
- 如果仅针对查询来说，索引越多查询的速度就越快
- 如果一个表的索引很多，就需要维护很多的B+树，这样我们在进行增删改的时候就要维护更多的索引树，会导致效率降低
6.对于MySQL单表来说，有没有性能的极限呢？
在突破了一定量的数据大小后，会导致索引的效率变低，所以单表的数据最好不超过500w条
