[数据结构与算法]学习笔记-浅谈MySql索引的数据结构与算法和索引的介绍

索引的数据结构

B-Tree（B树）

??B树是一种自平衡的树，为了实现高效的访问磁盘存取而设计的多叉平衡搜索树，B树中的每个节点的元素和子树都是有限的，除了跟节点，每个节点最多有M个元素，每个内部节点最少有 ?M/2?个子节点，向上取整。

B-Tree特点

1. 根节点至少有两个子节点
2. 树中每个节点至少有M(M>=2)个子节点
3. 除根节点和叶子节点，其他每个节点至少有ceil(m/2)个子节点（向上取整）、
4. 所有的叶子节点都在一层上
5. 假设每个非叶子节点中包含有n个关键字信息
   • ki(i=1…n)且关键字按升序排序K(i-1) < Ki
   • 关键字的个数n必须满足：[ceil(m/2)-1] <= n <= m-1
   • 非叶子节点的指针：p[1],p[2]…p[m]其中p[1]指向关键字小于k[1]的子树，p[m]的指向关键字大于k[m-1]的子树，其他p[i]指向关键字属于(k[k(i-1),k(i)])的子树。

B-Tree优点

1. 叶子节点具有相同的深度，叶子节点的指针为空
2. 所有索引元素不重复
3. 节点中的数据索引从左至右递增排序
   

B+Tree（B+树）

??B+树是一种特殊的B树，和B树的性质差别多，只是对B树的每个非叶子节点有指针域和数据域，而B树非叶子节点只有指针域而没有指针域，还有就是没有节点都会出现在叶子节点上，并且每个叶子节点都是用双链表的形式，方便更好的做范围查询。

B+Tree特点

1. 非叶子节点的子树指针域关键字树相同
2. 非叶子节点的子树指针p[i]，指向关键字值[k[i],k[i-1]]的子树
3. 非叶子节点仅使用索引。数据都保存在叶子节点中
4. 所有叶子节点均有一个指向下一个叶子节点的指针和指向前节点的指针

B+Tree优点

1. 非叶子节点不存储数据，只存储索引，可以存储更多的索引
2. 叶子节点用指针连接，提高区间访问的性能
3. 查询效率稳定、磁盘读写代价更低
   

Hash

??Hash索引是一种hash散列结构，它的存取速度非常快，Hash只支持等值查询，Hash索引只存储hash值适合字段长度较长，且字段选择性好的等值查询。

Hash优点

1. 对索引的key进行一次hash计算就可以定位出数据的存储位置
2. 很多时间Hash索引要比B+树索引更高效

Hash缺点

1. 仅能满足等值查询‘in’，‘=’，不支持范围查询
2. hash冲突问题

红黑树

??红黑树是一种自平衡的二叉查找树，是一种特殊化的AVL树，都是进行查询和删除操作时通过特定操作二叉树的平衡，插入和删除。它虽然比较复杂的，但它的最坏情况运行时间也非常良好的，并且在实践中是高效的。缺点就是当数据量大的时候层次很深(n个节点开平方根向上取整)

红黑树特点

1. 每个节点不是黑色就是红色
2. 根节点是黑色
3. 每个叶子节点（NIL）是黑色
4. 如果一个节点是红色的，则它的子节点必须是黑色的
5. 从一个节点到改节点子孙节点的所在位置包含相同树木的黑节点
   

Mysql的引擎

MyISAM

??MyISAM索引文件和数据文件是分离的（非聚集）

InnoDB

??InnoDB表数据文件本身就是按照B+Tree组织的一个索引文件，聚集索引叶子节点包含了完整的数据记录

MyISAM和InnoDB的异同

1. InnoDB支持事务，MyISAM不支持事务
2. InnoDB支持外键，MyISAM不支持外键
3. InnoDB是聚集索引，MyISAM是非聚集索引
4. InnoDB不保存表的具体行数，而MyISAM会专门维护应该变量保存表的记录数
5. InnoDB支持行锁（默认），MyISAM支持表锁（默认）
6. InnoDB表的必须有唯一的主键，而MyISAM非必须

MySql的索引辨析

索引分类

按数据结构划分： B+Tree索引、Hash索引、Fulltext索引(全文索引5.6后，MyISAM和InnoDB都支持)、R-Tree索引


按物理存储划分： 聚集索引、非聚集索引


按逻辑角度划分： 主键索引、唯一索引、普通索引、联合索引等

聚集索引和非聚集索引

聚集索引（聚簇索引）

??InnoDB中使用的了聚集索引，就是将表的主键用来构建一棵B+树，并且将整张表的行记录数据存放在该B+树的叶子节点中。聚集索引的叶子节点就是数据页，换句话说数据页存放的就是完整的每行记录。

聚簇索引的优点

1. 通过聚簇索引能获取完整的整行数据。
2. 对于主键排序查询和范围查询速度非常快

如果没有主键如何选择主键

??通常InnoDB索引不管是任何书籍和公司的MySql开发规范都强烈要求我们建一个主键并且最后是自增主键。因为是具有主键构建的B+Tree来存储数据，如果建表的时候没有主键，就会选择建表的唯一索引，选择唯一索引的字段为主键，如果建表的时候没有唯一索引，就会选择一个隐含列RowId(随机数)来做主键，然后就用这个主键来建立聚集索引。

非聚集索引（非聚簇索引）

??MyISAM就是使用了非聚集索引，B+Tree的叶子节点的数据域不是存储这条数据的记录，而是存向指向数据的一个key。

辅助索引（二级索引）

??聚簇索引只有在搜索条件中有主键是才能发挥作用，但是我们在实际的开发中的时候，大多数筛选查询都不是用id，都是用实际的义务字段。此时我们就需要根据义务需要，此时的B+Tree的叶子节点的数据域就会存主键的ID的地址，如果没有进行覆盖就会回表进行获取索引的数据。

回表和MRR

回表

??辅助索引的存在并不影响数据在聚簇索引中的组织，因为一张表可以有多个复杂索引。当通过辅助索引来寻找数据，InnoDB存储引擎会遍历辅助索引并通过叶子级别的节点干活去指向主键索引的主键，然后通过主键索引来找到一个完整的行记录，就称为回表。
??为什么需要回表一次，直接把完整的用户记录放到不就行了吗？如果把完整的记录都存在叶子节点，但是太占地方了，相当于没创建一个索引都需要拷贝一遍，并且如果有修改所有的索引都需要进行调整了，因此性能很低。

MRR

??很明显如果每查询一条记录都进行一次回表这样效率就比较低，MySql底层了Disk-Sweep Multi-Range Read（MRR，多范围读取）的优化措施，即先读取一部分二级索引记录，将它们的主键值排好序之后再统一执行回表操作。这样就减少了回表的次数，这样就节省一些IO开销。使用这个MRR优化措施的条件比较可靠，索引我们直接认为读取每条二级索引记录就立即执行回表操作。

主键索引

??主键索引它是一种特殊的索引，不允许有空值，就是我们建表的主键基于这个id来作为主键索引。

普通索引

??最基本的索引，没有任何限制


alter table table_name add index index_name(coll_name);


create index index_name on tbale_name(coll_name);

唯一索引

??与普通索引lies，不同的是所有列必须有唯一的值，但允许有空值


alter table table_name add unique index index_name(coll_name);


create unique index index_name on tbale_name(coll_name);

联合索引（组合索引/复合索引）

??在实际的开发中可能需要构建一个索引需要多个字段，例如index(a,b)就是将a,b两个组合起来构成一个索引。注意：多个字段都是建立在一棵B+树上的。

什么是最左匹配原则

??当建立了一个联合索引后，但是查询的时候必须遵守最左匹配原则，但满足了左边的字段，才会使用索引进行查询。

最左匹配原则示例

假设index(a,b,c)

全文索引

??它将存储于数据库的整本书或整篇文章中的任意内容信息找出来的技术。MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引。从InnoDB 1.2.x版本开始，InnoDB存储引擎开始支持全文检索，对应的MySQL版本是5.6.x系列。


alter table table_name add fulltext index index_name(coll_name);


create fulltext index index_name on tbale_name(coll_name);


注意：不管什么引擎，只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引。

自适应Hash索引

??InnoDB存储引擎除了我们前面所说的各种索引，还有一种自适应哈希索引，我们知道B+树的查找次数,取决于B+树的高度,在生产环境中,B+树的高度一般为3 ~ 4层,故需要3 ~ 4次的IO查询。
??所以在InnoDB存储引擎内部自己去监控索引表，如果监控到某个索引经常用，那么就认为是热数据，然后内部自己创建一个hash索引，称之为自适应哈希索引( Adaptive Hash Index,AHI)，创建以后，如果下次又查询到这个索引，那么直接通过hash算法推导出记录的地址，直接一次就能查到数据，比重复去B+tree索引中查询三四次节点的效率高了不少。
??InnoDB存储引擎使用的哈希函数采用除法散列方式，其冲突机制采用链表方式。注意，对于自适应哈希索引仅是数据库自身创建并使用的，我们并不能对其进行干预。

什么是密集索引和稀疏索引

密集索引： 叶子节点保存的不只是建值的，还保存了位于同一行记录里的其他列信息，由于密集索引决定了表的物理排列顺序，一个表只有一个物理排序顺序，所以一个表只能创建一个密集索引。
稀疏索引： 叶子节点仅保存了键位信息以及改行数据的地址，由于的稀疏索引只保存了键位信息和机器主键
??MyISAM存储索引，不管是主键索引，唯一索引还是普通索引都是稀疏索引；InnoDB存储引擎有且只有一个密集索引，所以密集索引就是InnoDB存储引擎里的聚簇索引，稀疏索引就是InnoDB存储里面的普通二级索引。

辨析索引覆盖（覆盖索引）

??覆盖索引是我们经常听见的名称，InnoDB存储引擎支持覆盖索引，就是从二级索引中就可以查询得到的记录，不需要再进行回表去聚簇索引中获取记录，因此可以减少了大量的IO操作，覆盖索引可以视为一种索引优化方式，而并不是一种索引类型。

索引的代价

??世界上从来没只有好处而没有代价的东西，虽然索引是一个好东西，但是我们在使用的时候一定要先了解使用索引的代价，它在空间上和时间带来的影响。

时间上的代价

??每一次对表中的数据进行增、删、改操作时都需要去修改各个B+Tree索引，而且B+Tree每层节点都是安装索引列的值从小到大的顺序而组成溜了双向链表。所以存储引擎需要额外的时间进行一些移位，页面分裂，页面回收等相关操作来维护号B+Tree的平衡。这样的对B+Tree的维护相关的操作必然对性能造成一定的影响。

空间上的代价

??每建立一个索引都要它建立一棵B+Tree，每一棵B+Tree的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，一棵很大的B+Tree由许多的数据页存储空间。

MySql的范式介绍

范式设计

什么设计范式

??范式来自英文Normal Form检测NF。MySql是关系型数据库，但是设计一个好的关系，必须满足一定的约束条件，此约束已经形成了规范，分层好几级，一级比一级要求严格。满足了这些规范的数据库是简洁的、结构明晰的同时，不会范式增、删、改操作异常。目前关系型数据库六种范式：第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、巴斯-科德范式（BCNF）、第四范式（4NF）、第五范式（5NF）。

第一范式

??第一范式关系必须满足索引属性不可再分即数据向不可分

第二范式

??第二范式必须满足第一范式，要求数据库中的每个实例或行可以被唯一地区分。通常在实现说需要在表上加一个列，来存储各个实例的唯一标识。

第三范式

??第三范式必须满足第二范式，指每个非主属性即不部分依赖也不传递依赖业务主键，也就是在第二范式的基础上消除非主键对主键的传递依赖。

反范式设计

??在这个互联网时代对查询响应的速度要求非常高，很明显在实际的业务查询中会大量的表存在关联查询，而大量的关联查询在数据量很大的时候非常影响性能；所谓反范式化就是为了性能考虑和读取效率得考虑而适当对数据库的设计范式要求进行违反，进行少量的冗余，也就是通常说的空间换时间。

范式化和反范式化的比较

范式化的优缺点

优点

1. 范式化的更新操作通常比反范式化要快。
2. 当数据较好的范式化时，就只有很少或者没有重复数据，所以只需要修改更少的数据。
3. 范式化的表通常比较小，可以更好的放在内存里，所以执行操作会更快。
4. 很少有多余的数据就检索列的表数据更少需要distinct或者group by语句。

缺点

1. 范式化设计通常需要关联
2. 关联的表比较多情况下一些索引策略无效。

反范式化的优缺点

优点

1. 反范式设计可以减少表的关联
2. 可以更好的进行索引优化

缺点

1. 存在数据冗余及数据维护异常
2. 对数据的修改需要更多的成本