索引，不光是我们再工作中时常用到的一个名词，在面试的时候也是逢考必面的知识点，索引可以让我们的速度提升千百倍效率，也可以让我们本来运行很ok的sql变的不那么“和谐”，接下来我们就聊聊索引。
一、什么是索引
MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结构。
我们可以简单理解为：快速查找排好序的一种数据结构。
或者理解为一本书的目录，个人认为重点是“有序”。
索引的本质就是数据库中字段值的复制，该字段称为索引的关键字；
索引也是一张表，记录保存了主键与索引字段，并指向了实际表数据；
索引往往通过复杂的数据结构（双向链表、hash、BTree/B+Tree、）实现；
MyISAM存储引擎的表支持主索引，InnoDB存储引擎的表支持聚簇索引(主索引)与非聚簇索引(辅助索引)索引优化使用。
二、主流索引查找算法
线性查找，是一个链表，要搜索的话，需要从第一个往后一个个找
二分查找，是线性查找的升级，也就是说二分查找是可以用线性查找的数据接口，但是算法不一样
二叉树查找，进一步提高性能，引入了二叉树
平衡二叉树，二叉树因为有平衡的问题，又进一步出现了平衡二叉树
B树，在平衡二叉树之后又发现了一个问题，之前的数据结构每一个节点都是一个行数据，这样的话对于磁盘的利用率是有问题的，因为我的数据要最终落到磁盘上，以一个节点为单位去读取磁盘效率是很低的
B+树，B树效率也有问题，出现了B+树，可以理解B+树是B树和线性的结合
二、索引 的分类
从索引存储结构划分：B Tree索引、Hash索引、FULLTEXT全文索引以及R Tree索引
从应用层次划分：普通索引、唯一索引、主键索引、复合索引
从键值划分：主键、辅助
从数据存储以及索引逻辑关系划分：聚集索引、非聚集索引
而Mysql索引主要有两种结构：B+Tree索引和Hash索引。我们平常所说的索引，如果没有特别指明，一般都是指B树结构组织的索引(B+Tree索引)。
接下来我们就一一介绍一下各个索引名词：
2.1、BTree 索引
BTree 全称 Balanced Tree，是一种很普遍的数据库索引结构，oracle默认的索引类型。
其特点是定位高效、利用率高、自我平衡，特别适用于高基数字段，定位单条或小范围数据非常高效。理论上，使用Btree在亿条数据与100条数据中定位记录的花销相同。
演算如下：
读取root节点，判断82大于在0-120之间，走左边分支。
读取左边branch节点，判断82大于80且小于等于120，走右边分支。
读取右边leaf节点，在该节点中找到数据82及对应的rowid
使用rowid去物理表中读取记录数据块(如果是count或者只select rowid，则最后一次读取不需要)
而由于Btree索引对结构的利用率很高，定位高效。当1千万条数据时，Btree索引也是三层结构(依稀记得亿级数据才是3层与4层的分水岭)。定位记录仍只需要三次I/O，这便是开头所说的，100条数据和1千万条数据的定位，在btree索引中的花销是一样的。
Btree索引的自我平衡（平衡扩张）借用下面几张图进行说明：
新建一个索引，索引上只会有一个leaf节点，取名为Node A，不断的向这个leaf节点中插入数据后，直到这个节点满；
当Node A满之后，我们再向表中插入一条记录，此时索引就需要做拆分处理：会新分配两个数据块NodeB & C，如果新插入的值，大于当前最大值，则将Node A中的值全部插入Node B中，将新插入的值放到Node C中；否则按照5-5比例，将已有数据分别插入到NodeB与C中；
无论采用哪种分割方式，之前的leaf节点A，将变成一个root节点，保存两个范围条目，指向B与C，结构如下图：
如果当根节点Node A也满了，则需要进一步拆分：新建Node E&F&G，将Node A中范围条目拆分到E&F两个节点中，并建立E&F到BCD节点的关联，向Node G插入索引值。此时E&F为branch节点，G为leaf节点，A为Root节点：
在整个扩张过程中，Btree自身总能保持平衡，Leaf节点的深度能一直保持一致。
参考文章：http://zsuil.com/?p=1184
2.2、B+Tree索引
MySQL数据库索引采用的是B+Tree结构，在B-Tree结构上做了优化改造，其特点：
只有叶子节点包含索引和数据
非叶子节点只存储索引值
叶子节点用指针连接，提高区间访问性能
对比B树来说，B+树范围查找时，只需要定位俩个节点的索引值，然后利用叶子节点指针进行遍历即可，而B树需要遍历范围内所有的节点数据，俩相对比，B+树效率更高
2.3、Hash 索引
Hash索引是基于Hash表实现，只有查询条件精确匹配Hash索引中的所有列时，才能够使用到Hash索引。也就是说，Hash索引只能用在等值查询，那么范围和模糊查询就不可以了；存储结构如下图：
对于Hash索引中的所有列，存储引擎都会为每一行计算一个Hash码，Hash索引中储存的就是Hash码。
Hash索引表中保存每一个Hash索引所代表的数据行的指针，由于Hash索引本身只存储Hash码，所以Hash索引结构比较紧凑，那么查询速度比较快。
2.2、FULLTEXT全文索引
全文索引,通过建立倒排索引,可以极大的提升检索效率,解决判断字段是否包含的问题.
例如: 有title字段,需要查询所有包含 "政府"的记录. 需要 like "%政府%"方式查询,查询速度慢,当查询包含"政府" OR "中国"的需要是,sql难以简单满足.全文索引就可以实现这个功能.
旧版的MySQL的全文索引只能用在MyISAM表格的char、varchar和text的字段上。
不过新版的MySQL5.6.24上InnoDB引擎也加入了全文索引，所以具体信息要随时关注官网，
-- 方式1、创建表的同时创建全文索引CREATE TABLE article ( id INT AUTO_INCREMENT NOT NULL PRIMARY KEY, title VARCHAR(200), body TEXT, FULLTEXT(title, body) ) TYPE=MYISAM; -- 方式2.通过 alter table 的方式来添加ALTER TABLE `student` ADD FULLTEXT INDEX ft_stu_name (`name`) ; -- ft_stu_name是索引名，可以随便起 -- 或者：ALTER TABLE `student` ADD FULLTEXT ft_stu_name (`name`);-- 方式3. 直接通过create index的方式CREATE FULLTEXT INDEX ft_email_name ON `student` (`name`); -- 也可以在创建索引的时候指定索引的长度：CREATE FULLTEXT INDEX ft_email_name ON `student` (`name`(20));
使用全文索引
使用全文索引的格式： MATCH (columnName) AGAINST ('string'); eg: SELECT * FROM `student` WHERE MATCH(`name`) AGAINST('聪'); 当查询多列数据时： 建议在此多列数据上创建一个联合的全文索引，否则使用不了索引的。 SELECT * FROM `student` WHERE MATCH(`name`,`address`) AGAINST('聪 广东');不知不觉写到这已经2k多字了，本期我们就写到这里，下期我们继续
探讨索引。
…………………………………分割线……………………………
不积跬步，无以至千里；不积小流，无以成江海。
我都墨迹这么半天了 ，你不点关注，不点赞，不收藏，还不转发，你想干啥！！！！
关注我，每天分享一些小知识点。分享自己的小心得，包含但不限于初、中、高级面试题呦！！！
