所在文集：数据库
本文的内容参考了：
索引的作用：空间换时间，加快查询的速度。
select * from student where name = 'Tom'
- 若
name字段没有索引：full table scan - 若
name字段有索引：减少scan的数目
索引的创建：基于某一列创建，由某一列上的数据组成。
create index <index_name> on students(name)
详细的语法：
CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name
[index_type]
ON tbl_name (index_col_name,...)
[index_option]
[algorithm_option | lock_option] ...
- index_type: USING {BTREE | HASH}
- index_col_name: col_name [(length)] [ASC | DESC]
- 如果是CHAR，VARCHAR类型，length可以小于字段实际长度
- 如果是BLOB和TEXT类型，必须指定 length
-
index_option: KEY_BLOCK_SIZE [=] value
| index_type
| WITH PARSER parser_name
| COMMENT 'string' - algorithm_option: ALGORITHM [=] {DEFAULT|INPLACE|COPY}
- lock_option: LOCK [=] {DEFAULT|NONE|SHARED|EXCLUSIVE}
索引的数据结构
Hash 表
- 数组结构：key 为列的值，value 为该行在数据库表的位置，在数组中的位置由 key 的哈希值确定。
- 优点：查找、插入、修改、删除的时间复杂度为
O(1) - 缺点：无序，对于范围的查找不行，例如
select * from students where age < 30 - InnoDB 并不支持哈希索引
B 树
- 数组结构：参见 多路搜索树 & B 树 & B+树 学习笔记
- 查找、插入、修改、删除的时间复杂度为
O(logN) - 过程：
select * from students where name='Tom'，在 B- 树中找到值为 Tom 的结点，时间复杂度为O(logN)，得到 Tom 对应的行在数据库表中的位置。
**B树被作为实现索引的数据结构被创造出来，是因为它能够完美的利用“局部性原理”：
- 内存读写块，磁盘读写慢，而且慢很多；
- 磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载更多的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘 IO，提高效率；
- 局部性原理：软件设计要尽量遵循 “数据读取集中” 与 “使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO；
B树为何适合做索引？
- 由于是 m 分叉的，高度能够大大降低；
- 每个节点可以存储多个记录，如果将节点大小设置为页大小，例如 4K，能够充分的利用预读的特性，极大减少磁盘 IO；
B+树
- 数组结构：参见 多路搜索树 & B 树 & B+树 学习笔记
- 查找、插入、修改、删除的时间复杂度为
O(logN) - 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；
- 叶子之间，增加了链表，获取所有节点，不再需要中序遍历；
B+ 树比 B 树有更优的特性：
- 范围查找，定位 min 与 max 之后，中间叶子节点，就是结果集，不用中序回溯；（这是因为在 B+ 树中叶子之间，增加了链表，获取所有节点，不再需要中序遍历）
- 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；
- 非叶子节点，不存储实际记录，而只存储记录的 key 的话，那么在相同内存的情况下，B+ 树能够存储更多索引；
问题：哈希(hash)比树(tree)更快，索引结构为什么要设计成树型？
索引设计成树形，和 SQL 的需求相关。对于这样一个单行查询的 SQL 需求：
select * from students where name='Tom'
确实是哈希索引更快，因为每次都只查询一条记录。
但是对于排序查询的 SQL 需求，例如：
- 分组：
group by - 排序：
order by - 比较：
<、>
哈希型的索引，时间复杂度会退化为 O(n)，而树型的“有序”特性，依然能够保持 O(logN) 的高效率。
索引的一些注意事项
有的情况下即使定义了索引也不会使用：
where name != 'Tom'
where name <> 'Tom'
where name not in ('Tom', 'Lily')
where name like '%To%' // %出现在最左边，无法进行比较
联合索引 Composite Index：
create index <index_name> on students(name, age, address)
对于联合索引，只有符合最左前缀的查询才会被优化：
where name = 'Tom' // 优化
where name = 'Tom' and age = '12' // 优化
where age = '12' // 不优化
where age = '12' and address='Shanghai' // 不优化
前缀索引：
假设 students 表包括 first_name 和 last_name：
- 若只对
last_name建立索引，则last_name（姓）的选择性太低。 - 若对
first_name和last_name建立联合索引，则索引太长，导致插入/更新/删除 数据行时维护索引的时间较长。 - 因此可以对
first_name取前缀：create <index_name> on students(last_name, left(first_name, 3))
不需要建立索引的情况：
- 表中行数少
- 某一列的选择性 selectivity 较低。例如 性别
gender列只有 M 和 F 两种值，则无需对该列建立索引。
一些注意事项：
- 索引不能为空。因此任何包含
null值的列都不会包含在索引中，即使显示地对该列建立索引也不会提高性能。 - 连接列不会使用索引：
select * from students where first_name = 'San' and last_name = 'Zhang'; // 推荐使用
select * from students where first_name || last_name = 'San Zhang'; // 不推荐使用
- 带
%的like语句会降低索引的效率 - 注意
NOT的使用
where age != '20' // 不推荐使用
where age < '20' or age > '20' // 推荐使用
MyISAM 与 InnoDB 的索引差异
数据库的索引分为：
- 主键索引（Primary Index）
- 普通索引（Secondary Index）
MyISAM 的索引
MyISAM 的索引与行记录是分开存储的，叫做非聚集索引（UnClustered Index）。
其主键索引与普通索引没有本质差异：
- 有连续聚集的区域单独存储行记录
- 主键索引的 B+ 树叶子节点，存储主键，与对应行记录的指针
- 普通索引的 B+ 树叶子结点，存储索引列，与对应行记录的指针
- 主键索引与普通索引是两棵独立的索引 B+ 树，通过索引列查找时，先定位到 B+ 树的叶子节点，再通过指针定位到行记录。
MyISAM 的表可以没有主键。
InnoDB 的索引
InnoDB 的主键索引与行记录是存储在一起的，故叫做聚集索引（Clustered Index）。
- 没有单独区域存储行记录
- 主键索引的 B+ 树叶子节点，存储主键，与对应行记录（而不是指针）
- 普通索引的 B+ 树叶子结点，存储索引列，与对应行记录的指针
因此，InnoDB 的主键查询是非常快的，因为主键索引的 B+ 树和行记录是在一起存储的。
InnoDB 的表必须要有聚集索引：
- 如果表定义了主键，则主键就是聚集索引；
- 如果表没有定义主键，则第一个非空 unique 列是聚集索引；
- 否则，InnoDB 会创建一个隐藏的 row-id 作为聚集索引；
聚集索引，也只能够有一个，因为数据行在物理磁盘上只能有一份聚集存储。
InnoDB 的普通索引可以有多个，它与聚集索引是不同的：普通索引的叶子节点，存储主键（也不是指针）。
举个例子
有一个数据表 t(id PK, name KEY, sex, flag); 有如下数据：
1, shenjian, m, A
3, zhangsan, m, A
5, lisi, m, A
9, wangwu, f, B
可以看出 id 是主键索引（Primary Index），name 是普通索引（Secondary Index）。
如果采用 MyISAM，索引和行记录的结构如下，可以看出：
- 行记录单独存储
-
id为 PK，有一棵id的索引树，叶子指向行记录 -
name为 KEY，有一棵name的索引树，叶子也指向行记录
如果采用 InnoDB，索引和行记录的结构如下，可以看出：
-
id为 PK，行记录和id索引树存储在一起 -
name为 KEY，有一棵name的索引树，叶子存储id
当：select * from t where name=‘lisi’; 时，会先通过 name 辅助索引定位到普通索引 B+ 树的叶子节点得到 id=5，再通过聚集索引（即主键索引）定位到行记录。所以，其实扫了2遍索引树：
