基础-索引及其数据结构

索引

为了提高数据库中主键以外的列的搜索效率，所以可以对这些列建立索引，使得DBMS保存经过排序的列表，实现高效查找
1.改善检索性能，但是降低了数据插入，删除，修改时候的性能，在数据变动之后也必须动态更新索引，因此索引不适合建立在改动频繁的字段上，而且需要定期检查不断更新
2.占据大量的存储空间
3.利于数据过滤和排序的性能，经常ordered by就需要考虑建立索引了
4.索引可以建立在多个列的组合上

CREATE INDEX pro_name_id
ON PRODUCTS(prod_name)

MySQL有哪几种索引类型

1.哈希索引
InnoDB存储引擎支持的哈希索引是自适应的，，根据表的情况自动生成哈希索引，不能人为生成
2.B+树索引
目前关系型数据库查找最常用最有效的索引
他能找到的是被查找数据行所在的页，然后数据库把页读到内存里，再在内存中查找数据
3.全文索引

B+树

高度平衡，叶子存放数据，并且叶子间以双向链表的数据结构连接的多路平衡查找树

是由B树和索引的顺序访问方法演化来的，现实中几乎没有使用B树的情况了

他是为磁盘或者其他直接存取辅助设备而设计的一种多路平衡查找树

B+树的插入和删除操作

B+树索引

B+索引就是B+树在数据库中的实现，其中树的高度一般在2-4层，也就是说查找某一个键的行记录最低只需用2-4次的IO, 一般的机械键盘每秒100次IO，也就是说每次键值查询最多只需0.02-0.04s
B+树索引分为聚集索引和辅助索引

聚集索引
InnoDB中存储引擎表是索引组织表，表中数据按照主键的顺序存放，聚集索引就是按照每张表的主键构造一颗B+树，叶子节点存放的就是这张表的行记录数据，聚集索引的叶子节点叫数据页，数据页之间通过双向链表进行连接，数据也是索引表的一部分

每张表只能有一个聚集索引，一棵B+树进行排序

优势：
一个就是物理上不必连续存储
再一个就是对于主键的排序查找和范围查找速度非常快，
比如说在注册用户的表中查询最后10位注册的用户，可以快速找到最后一个数据页，一次读出10条；
又比如想找主键某一范围内的数据，通过叶子节点的上层中心节点就可以得到页的范围

聚集索引的存储是逻辑上连续的，不是物理上连续的，表现在
第一：数据页也就是节点之间用双向链表链接，页按照主键的顺序排序
第二：每个数据页中的数据记录也是用双向链表维护的，物理存储可以同样不连续

辅助索引（也称非聚集索引）
叶子节点不包含行记录的全部数据，除了包含键值外，还包含一个书签，书签告诉存储引擎InnoDB哪里可以找到与索引对应的行数据，他的辅助索引的书签就是对应行数据的聚集索引键

一张表可以有多个辅助索引，跟聚集索引不影响，可以用作快速定位到某一行数据，使用辅助索引寻找数据时，InnoDB存储引擎会遍历辅助索引然后通过叶节点的书签指针获得主键索引的主键，再通过聚集索引树的搜索找到这个主键对应的行记录

哈希索引

InnoDB存储引擎用的是哈希算法，哈希函数是取余操作，冲突机制采用链表结构
哈希索引只能用来进行等值查询，对于范围查询只能逐个搜索

全文索引

全文索引顾名思义就是对数据库中存在的任意内容信息查找出来，而不是仅仅根据字段找到某一行数据，比如LIKE语句，对内容进行模糊查询

语句：
SELECT * FROM fts_a
WHERE MATCH(body)
AGAINST ("abc" IN NATURAL LANGUAGE MODE)---全文索引关键字

1.倒排索引
全文索引通常是使用倒排索引来实现的，他在辅助表中存储单词和单词自身存放的位置的这样一个映射，用关联数组来实现的，结构是单词加上单词所在的文档的ID和文档中位置的组合

2.InnoDB存储引擎中的全文搜索
全文搜索表有两列，一列是word一列是ilist，ilist包含了文档ID和对应位置
一是采用倒排索引来实现，他的内部有六张辅助表存放在磁盘上，每张表根据单词内容的latin编码进行分区；

二是FTS索引缓存来提高全文索引的性能
他是采用红黑树的数据结构，他根据word，ilist进行排序，在插入时就进行更新，然后存储引擎会批量对辅助表进行更新