索引 index

索引 (index)，好比书的目录 (index)
本质上：用来加快查找的效率

例： 如果想找 id 为 8 的学生信息

如果数据库中没有索引，此时查找的时候就需要把数据库的整张表遍历一遍
索引就是为了避免数据库进行顺序查找，提高查找效率

若没有索引，此时的查找过程，就相当于一个"顺序表查找"，即：依次遍历每条记录，来查找记录

若是针对顺序表查找，顺序表是在内存中的，内存访问速度快，并且数据也没那么多
若是针对数据库顺序查找，数据库的数据是在磁盘上，磁盘访问速度更慢，并且数据量也可能非常多，这个速度可能就会很慢

概念

索引是一种数据结构，可以帮助我们快速的进行数据的查找

索引可以考虑的数据结构

二叉树(二叉搜索树)，如果比较平衡，那么查找效率：O(logN)
哈希表，查找效率：O(1)
数据库的索引可以考虑使用哈希，但会出现一些问题：
.
例如： 查找 id < 6 并且 id > 3的学生信息

select * from student where id > 3 and id < 6;
像这样的操作，哈希表无法完成

哈希只能处理相等的情况，不能处理 >，<，>=，<=，between and… 的情况
哈希的查找过程： 把 key 代入哈希函数，计算得到下标，再根据下标取到对应的链表，再去遍历比较 key 是否相等

考虑使用二叉搜索树：
二叉搜索树内部元素是有序的(中序遍历结果有序)
.
例如： 查找 id < 6 并且 id > 3的学生信息

select * from student where id > 3 and id < 6;

先找到 id 为6 的元素
再找到 id 为 3 的元素
中序遍历，3 和 6 之间的结果就是想要的结果
中序遍历效率 ： O(N)

二叉搜索树相比于哈希表，虽然可以处理范围查找，但是处理效率不高

原因：

• 二叉搜索树每个节点最多两个叉，当数据量比较大的时候，树的高度较高(影响递归层次)，最终的操作效率也就越低
• 二叉搜索树直接获取到中序遍历，也不高效 O(N)

B / B+Tree

真实的索引结构，是一种 N叉搜索树 —— B+ 树
要想认识 B+ 树，需要先认识 B树 (B- 树)
(有B 树，B+ 树，没有 B减树)

二叉树用来做索引的问题：

• 如果索引数据很多，树的层次会很高 (只有左右两个子节点)，数据量大时查询会很慢
• 二叉树每个节点只存储一个记录，一次查询在树上找的时候花费磁盘 IO 次数较多

B Tree 特点：

• 不再是二叉搜索，而是 N 叉搜索，树的高度会降低，查询速度加快
• 叶子节点，非叶子节点，都可以存储数据，且可以存储多个数据
• 通过中序遍历，可以访问树上所有节点
• 每个节点存的数据的个数，与该节点的度是相关的
  度 = 存的数据个数 + 1

B+ 树

B+ 树 特点：

• 和 B树 相比，每一层的元素都链接到了一起
• 数据只在叶子节点中保存，非叶子节点上只保存一些辅助查找的边界信息

B+ 树 改进优点：

• 仍然是 N 叉树，层级小高度低，非叶子节点不再存储数据，数据只存储在同一层的叶子节点上，B+树 从根到每一个节点的路径长度一样，而 B树不是这样
• 叶子之间，增加了链表 (图中箭头指向)，获取所有节点，不再需要中序遍历，使用链表的 next 节点就可以快速访问到
• 范围查找方面，当定位 min 与 max 之后，中间叶子节点，就是结果集，不用中序回溯（范围查询在SQL中用得很多，这是B+树比B树最大的优势）
• 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储
• 非叶子节点，不存储实际记录，而只存储记录的 key 的话，那么在相同内存的情况下，B+树 能够存储更多索引，索引在内存中占用的实际开销也不高
• B树，叶子节点和非叶子节点，都用来存储数据，且都存放在磁盘上，在查找的过程就会反复进行磁盘 IO 操作
  B+树，叶子节点放到磁盘上，非叶子节点放到内存里，减少了磁盘的 IO 操作，查找效率就高了

目的

加快查询效率，但会减慢插入 / 修改 / 删除的效率 (需要同步调整索引结构)

索引也会占用额外的空间 (本质上是在用空间换时间)

使用场景

应用在经常查询但是很少修改的场景上

使用

创建主键约束、唯一约束、外键约束时，会自动创建对应列的索引

给具体的表中某列加索引的时候，加在主键上的索引和加在其他列上的索引是完全不一样的

加在主键的索引，叫：主键索引

主键索引的叶子节点存的是数据的完整记录
其他索引的叶子节点村的就是主键的 id
例： 如果按 name 查找，先通过搜索 “王五” 对应的主键 id，再根据主键 id 去主键索引中查找到具体记录 (回表)

查看索引

show index from [ 表名 ]；

创建索引

create index 索引名 on [ 表名 ] (字段名)；

比较耗时

删除索引

drop index 索引名 on [ 表名 ]；

比较耗时

主键索引不能删除，删除会报错！

索引总结

• 创建 / 删除索引都是耗时操作
• 索引改善检索操作的性能，但降低了数据的插入、修改、删除的性能，在执行这些操作时，DBMS必须动态的更新索引
• 索引数据可能要占用大量的储存空间
• 索引用于数据排序和数据过滤
  如果经常以某种特定的顺序排序数据，则该数据可能适合做索引
• 索引必须唯一命名