DBMS索引技术

Q：为什么要引入索引？

执行器要向存储引擎要数据，存储引擎要知道“数据”在哪里。
（页表？ 页表并不知道页面内容是什么）
此时如果不用索引，则要进行顺序查找，复杂度O（n） 索引可以降低复杂度，争取降低到O（logn） 甚至O（1）

索引的目标

帮助我们快速定位目标所在的内存地址，定位目标所在的磁盘页面。

分类：基于索引所用的数据结构，可以分为哈希表索引、基于树的索引。
要考虑的问题： 数据组织问题，存储何种信息；并发访问问题

索引数据结构
一个索引项=搜索码+指针
一组索引项构成的表格称为一个索引文件

两种基本的索引类型：

• 顺序索引：搜索码按顺序组织
• 散列（哈希）索引：搜索码按照某个哈希函数平均分布到若干个桶中

相关数据结构

哈希表：
适合等值查询，如果是范围查询，那就是要把表都扫一遍了。。。

有序数组:
显然做查询很不错，无论是点查询（二分）还是范围查询。但是插入删除要移动，开销大。

二叉搜索树：
查找O（log n） ，维护为平衡二叉树，也要O（logN）

二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

如果只是二叉树，那么树的高度太高，每一次查询都要访问一次磁盘。（对于树的每一个层级的访问都要访问一次磁盘）

为了让一个查询尽可能少地读取磁盘，使用多叉树（N=1200）

其他：
跳表（redis）
LSM树

note：数据库底层存储的核心基于这些数据模型的。
mysql中，索引是在存储引擎实现的，所以没有统一的的索引标准。

InnoDB存储引擎

B+树索引模型
每一个索引在 InnoDB 里面对应一棵 B+ 树。一个表对应多个B+树，一个主键索引树和多个非主键索引树。

create table T(id int PRIMARY KEY,k int NOT NULL,name VARCHAR(16),INDEX(k)) ENGINE=INNODB;

在k上也建立了非主键索引。

查找主键字段时，只需要查ID这颗B+树（叶子存的是整行数据）
查找非主键字段时，先查k对应的B+树，找到对应主键，然后再查ID对应的B+树（叶子存的是主键数据）—多查一次（叫做回表）

另外，InnoDB中，主键索引是聚簇索引。

索引维护
插入可能导致页分裂（1->2 空间利用率减半）
删除可能页合并
（这个应该算是B+树的性质）

有的建表规范 要求建立自增主键（NOT NULL PRIMARY KEY AUTO_INCREMENT） 符合递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。（来自极客时间） 另外一个原因…如果要在其他字段上建立索引，那么叶子内容是自增主键，占用的空间更小（INT 4bytes LongInt 8 Bytes）

业务字段做主键的场景：KV场景
要求：1. 只有一个索引 2. 该索引必须是唯一索引

索引优化

覆盖索引

eg. select id from T where k between 3 and 5 在查询中，索引k的叶子结点已经包含了主键id的信息，所以：索引k已经“覆盖了”我们的查询请求，被称为覆盖索引

什么时候要建立？

市民表如下：

	create table ttuser(id int(11) not NULL,id_card varchar(32) DEFAULT NULL,name varchar(32) DEFAULT NULL,age int(11) DEFAULT NULL,ismale tinyint(1) DEFAULT NULL,primary key(id),key id_card (id_card),key name_age(name,age) //这里建立了联合索引)ENGINE=INNODB;

如果有身份证号查询市民信息，那么身份证号上建立索引即可。
如果频繁利用身份证号，查询市民姓名，那么可以建立联合索引。它可以在这个高频请求上用到覆盖索引，不需要回表查找整行记录，减少语句的执行时间。

当然，维护索引有代价，所以这样的冗余索引是否需要建立要根据实际情况考虑。

最左前缀原则

从左到右使用索引中的字段，一个查询可以只使用索引中的一部分，但只能是最左侧的部分。
例如索引 key idx(a,b,c)支持按照a/ a,b/a,b,c 这三种组合进行查找，但不支持b,c查找

eg.

create table test(
a int ,
b int,
c int,
key idx(a,b,c)
);

通俗地说，有了（a，b）联合索引，就不需要建立 （a） 索引了

所以我们思考一个问题：在建立索引的时候，如何安排索引内的字段顺序？

如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的

所以之前的市民表，我们建立（身份证号，姓名）的联合索引，可以支持 “根据身份证号查询地址”的需求。

其他补充： 对于二级索引，会默认和主键做联合索引。

索引下推

mysql 5.6之后：
在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。