Mysql索引详解

原文链接：https://blog.csdn.net/qq_32679835/article/details/94166747

一、为什么需要索引？（索引的优缺点）

1、索引产生的意义

没有索引行不行？答案是肯定的，可以不使用索引，在数据库中将数据整齐的排列在磁盘阵列中，当获取数据的时候只需要逐个搜索，并返回结果，但是 如果开发的应用有几百上千万甚至亿级别的数据，那么不深入了解索引的原理， 写出来程序就根本跑不动，光查一个数据库就得好几天，因此就需要索引，能够快速的查找的需要的数据。

2、索引的优缺点

• 优点

1、极大地加速了索引过程，减少IO次数
2、创建唯一索引，保证了数据库表中的唯一性
3、加速了表与表之间的连接
4、针对分组和排序检索时，能够显著减少查询查询中的分组和排序时间

• 缺点

1、索引表占据物理空间
2、数据表中的数据增加、修改、删除的同时需要去动态维护索引表，降低了数据的维护速度

二、索引的分类

1、唯一索引：表上一个字段或者多个字段的组合建立的索引，这些字段组合起来能够确定唯一，允许存在空值（只允许存在一条空值）
2、非唯一索引：表上一个字段或者多个字段的组合建立的索引，可以重复，不需要唯一
3、主键索引：（主索引）根据主键pk_clolum（length）建立索引，不允许重复，不允许空值；
4、聚合索引：表中记录的物理顺序与键值的索引顺序相同
5、非聚合索引：表中记录的物理顺序与键值的索引顺序无关
6、全文索引：在某个字段设置全文索引后，根据特定语法查找满足条件的字段;

1、全文搜索在 MySQL 中是一个 FULLTEXT 类型索引。FULLTEXT 索引在 MySQL 5.6 版本之后支持 InnoDB，而之前的版本只支持 MyISAM 表。
2、目前只有char、varchar，text 列上可以创建全文索引。
3、 like “value%” 可以使用索引，但是对于 like “%value%” 这样的方式，执行全表查询

7、普通索引：用表中的普通列构建的索引，没有任何限制
8、组合索引：用多个列组合 构建的索引，但是在使用过程中有诸多规则，遵循最左前缀原则，顺序至关重要
9、Hash索引（Memory存储引擎）是通过索引列的值计算出hashCode,之后在相应的物理位置存取索引列的值，由于hashCode的唯一性，因此Hash索引不能进行范围查找或者是顺序查找。

三、B树-数据库索引原理

转载自博客：https://blog.csdn.net/endlu/article/details/51720299
2019.8.26补充：https://www.cnblogs.com/nullzx/p/8729425.html（关于B树与b+树更通俗）

1、B树（平衡多路查找树）

特性：
（关键字个数 = 儿子节点个数-1、每一个关键字按照升序排序、非叶子结点也存储数据、根节点至少2个子女，非叶结点至少ceil(m/2)个子女）

• 树中每个结点最多含有m个孩子（m>=2）；
• 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
• 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
• 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
• 每个非终端结点中包含有n个关键字信息： (P1，K1，P2，K2，P3，…，Kn，Pn+1)。其中：
  a) Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
  b) Pi为指向子树根的接点，且指针P(i)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
  c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

2、B树插入删除

实例引用：https://www.cnblogs.com/nullzx/p/8729425.html

2.1、插入

1）根据要插入的key的值，找到叶子结点并插入。
2）判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
3）以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。(核心思想：找到中间值，提升为父节点，之后分裂为左右)

2.2、删除

1 ） 找到下一个记录，之后用下一个记录代替当前记录的位置
2 ） 当前节点个数大于ceil(m/2)-1,直接删除
3 ） 当前节点个数大于ceil(m/2)-1，跟兄弟节点借一个，前提是兄弟节点个数大于ceil(m/2)-1，兄弟节点借的节点上移，父节点ke下移
4 ）兄弟节点个数小于等于ceil(m/2)-1，父节点下移之后与兄弟节点合并

3、B+树

实例引用：https://www.cnblogs.com/nullzx/p/8729425.html

B+树特有：
1.有n棵子树的结点中含有n个关键字； (而B树是n棵子树有n-1个关键字)
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)
4.关键字按照从小到大的顺序排列

3.1 B+树插入

1. 根节点，直接插入就可以了
2. 叶子结点：由于在B+树中叶子结点实际保存了了数据，因此在插入B+树后如果当前节点小于m-1,直接插入；否则就将当前节点分解，左叶子结点包含前ceil(m/2)个，后ceil(m/2)+1记录到右节点，将ceil(m/2)记录的key进到父节点（父节为索引类型）
3. 索引节点：若当前结点key的个数小于等于m-1，则插入结束。否则，分裂左右，左前(m-1)/2个节点，右为后边的节点，之后选择（m-1）/2插入到父节点

3.2 B+树删除

4、B+树的优势

1、查找：B+树磁盘读写次数更低
因为B+树非叶子结点只是相当于一个索引，会将所有关键字具体信息都存储叶子结点，也就导致B+树能够存储更加多的关键字数量，构造的树更加矮胖，一次性读入内存的关键字数量增加，IO读写次数减少

1、 在索引查找的时候，B树的搜索方式是首先找到一个搜索下界，也就是满足条件的最低值，之后通过中序遍历的方式查找，而B+树在查找到搜索下界后，直接通过链指针开始查找关键字信息
2、范围查找：B树从二叉树的下限一直中序遍历，知道查找到二叉树的上线，而B+树知道二叉树下限后，直接链表查找
2、B+tree的查询效率更加稳定
由于非终结点不存储数据，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

5、B树与B+树的差别

引用自：https://blog.csdn.net/q936889811/article/details/79780307
1、B树的同一键不会出现多次，可能在叶子节点上也可能在非叶子节点上； b+树的键一定会出现在叶子节点上，同时也可能在非叶子节点上重复出现。
简单的说，b+树的非叶子节点存储的都是键值，键值对应的具体数据都存储在叶子节点上。
2、b数据的每个节点存储的是真是数据，会导致每个节点的存储的数据量变小，所以整个b树的高度会相对变高。随着数据量的变大，维护代价也增加； b+树的非叶子节点只存储的是键值，相对而言，一个非叶子节点存储的记录个数要比b树多的多。
3、b+树是横向扩展，随着数据增加，会变成一个矮胖子，b树是纵向扩展，最终树的高度越来越高（高瘦子）。
4、b树的查询效率与键在b树的位置有关系，在叶子及诶单的时候最大复杂度与b+树相同；b+树复杂度对某个建成的树是固定的。
5、 b树的键的位置不固定并且整个树结构中只出现一次，增删改查操作复杂度逐渐加；b+树中非叶子节点对于叶子节点来说就像一个索引，增删改的时候只要找到键值（索引）的位置，再一层层的向下找即可，只有在遇到一个节点存储满了会对b+树分裂。
6、 b树种所有的数据都只存储一份；b+树除存储了所有数据的叶子节点外，还有之存储键值数据的非叶子节点。所以，b+树比b树会多占存储空间，多占的空间就是b+树的非叶子节点的所有空间。

四、聚合索引与非聚合索引

聚合索引与非聚合索引是一种存储方式，而不是一种单独的索引类型

前提概念：
1、按照索引的键是否为主键来分为“主索引”和“辅助索引”，使用主键键值建立的索引称为“主索引”，其它的称为“辅助索引”
2、聚簇索引的辅助索引的叶子节点的data存储的是主键的值，主索引的叶子节点的data存储的是数据本身，也就是说数据和索引存储在一起，并且索引查询到的地方就是数据（data）本身，那么索引的顺序和数据本身的顺序就是相同的；
而非聚簇索引的主索引和辅助索引的叶子节点的data都是存储的数据的物理地址，也就是说索引和数据并不是存储在一起的，数据的顺序和索引的顺序并没有任何关系，也就是索引顺序与数据物理排列顺序无关。
3、两者相同点就是通过B+树结构来构造B树索引

1、聚合索引（InnoDB存储引擎需要）

定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。

1、选择B+树作为存储结构
2、聚合索引必须有主键，没有主键就会选择Unique key作为主键，没有Unique则会在系统内部生成rowid作为主键，因此主键不宜过长，使得辅助索引过大，主键如果不是单调的就会造成B+Tree频繁的分裂调整
3、在InnoDb上会选择自增字段作为主键，是为了维持B+树的分裂特性，顺序添加到当前索引的后续位置，当达到最大就会分裂产生新的页，也不需要移动原有的顺序
4、聚合索引主索引和辅助索引，主索引叶子结点存储键值对应的数据本身，辅助索引叶子结点存储主键键值
5、由于辅助索引存储的是主键键值，因此按照辅助索引搜索的时候需要检索两遍，第一遍找到对应的主键，第二遍在主索引到达叶子结点中找到数据

2、非聚合索引（MyIsam）

定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。

1、选择B+树作为存储结构
2、非聚合索引有主索引和辅助索引（两个索引几乎一样），但是主索引不允许为空，现在就需要考虑在索引分类中介绍的非聚合索引的概念，由于物理顺序与索引顺序不同，因此每一个叶子节点存储的是指向键值对应的数据的物理地址（数据记录的地址）
3、非聚簇索引的数据表和索引表是分开存储的
4、获取数据的方式是首先根据B+树获取索引，取出对应数据记录的地址，之后再去读取相应的数据记录
5、只有在MyISAM中才能使用FULLTEXT索引。(mysql5.6以后innoDB也支持全文索引)
6、辅助索引的意义：如果给出的查询条件不是主键，此时就使用辅助索引，并且使用辅助索引不需要使用主索引

1、使用聚合索引的场景：

• 某列包含小数目的不同值
• 排序和范围索引（主键递增）
  2、使用非聚合索引的场景：
• 某列包含大数目的不同值（因为在叶子节点不需要去保存数据，只需要保存地址）
• 频繁更新的列，因为非聚集索引添加记录时，不会引起数据顺序的重组

3、InNoDB与MyISAM异同

博客（自己还未阅读）：https://www.cnblogs.com/y-rong/p/8110596.html

1、InnoDB 支持事务，支持行级别锁定，支持 B-tree、Full-text （InNoDB从1.2.X版本开始支持全文搜索的技术）等索引，不支持 Hash 索引，但是给了又有一个特殊的解释：InnoDB存储引擎 是支持hash索引的，不过，我们必须启用，hash索引的创建由InnoDB存储引擎引擎自动优化创建，是数据库自身创建并使用，DBA（数据库管理员）无法干预；
2、MyISAM 不支持事务，支持表级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
3、Memory 不支持事务，支持表级别锁定，支持 B-tree、Hash 等索引，不支持 Full-text 索引；
4、MyISAM引擎不支持外键，InnoDB支持外键
5、MyISAM引擎的表在大量高并发的读写下会经常出现表损坏的情况
6、对于count()查询来说MyISAM更有优势，MyISAM直接通过计数器获取。InnoDB需要通过扫描全部数据，虽然InNoDB存储引擎是支持行级别所，InNoDB是行级别锁，是where对他主键是有效，非主键的都会锁全表的
7、MyISAM引擎的表的查询、更新、插入的效率要比InnoDB高，如果你的数据量是百万级别的，并且没有任何的事务处理，那么用MyISAM是性能最好的选择。并且MyISAM可以节省很多内存，因为MyISAM索引文件是与数据文件分开放置，并且索引是有压缩，内存使用率提高不少
8、平台承载的大部分项目是读多写少的项目，MyISAM读性能比InNoDB强很多

4、InNoDB存储引擎内幕略读

1、版本功能

2、关键特性

（1）插入缓存：正常插入自增ID速度非常快，但是如果使用UUID（防止注入式攻击，当我们使用主键自增的时候，需要删除一个东西的时候，一般都是id=？。这样的话我就可以在url中修改这个id的值，这样可能就被人删除了其他东西，UUID这个就是给主键id加上一层锁，使它不暴露给用户）者中随机插入（非连续）的值，此时需要离散的访问非聚集索引页，不是直接插入索引页，而是判断非索引也是否在缓冲池中，若在，则直接插入，若没在则放入Insert Buffer中，在Insert Buffer 中合并后插入到索引页，提高了插入性能

InsertBuffer使用条件

1. 索引是辅助索引
   2、索引不是唯一的

（2）两次写
避免在处理事务时候发生宕机，虽然说事务操作可以日志恢复，但是如果宕机的时候完全删除当前页，如果，doubleWrite，一部分为内存中doublewrite buffer ,大小为2M，另一部分物理磁盘表空间中连续的128个页。缓冲池的脏页刷新的时候，首先会刷新到doublewrite buffer中，之后才会写入到各个表空间文件，遇到宕机，只需要从共享空间doublewrite中找到该页的副本恢复，之后重做日志
（3）自适应hash索引
InNoDB会监控对表上的各索引页查询，如果观察到建立hash索引可以带来速度提升，则建立hash索引，自动根据访问评率和模式来自动为某些热点也建立索引
（4）异步io
AIO可以将多个IO请求进行IO Merge，当一个IO请求发出后，可以立即发出另一个IO请求，当所有IO请求发送完毕，等待IO操作完成

3、全文索引

使用倒排索引来实现，两种表现形式：
(1)inverted file index{单词，所在文档id}
(2)full inverted index{单词，（ 单词所在文档，在具体文档中的位置）}

4、锁

1、Recored Lock:当个行记录上锁
2、Gap Lock:间隙锁，锁定一个范围，但不包含记录本身
3.Next-Key Lock:锁定一个范围，并且锁定记录本身
4、InNoDB存储影青通过通过Next-Key Locking 来避免幻读问题

五、组合索引（覆盖索引）

基于多个字段创建的索引就是组合索引。

组合索引规则：
1、最左原则：索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种组合进行查找，但不支持 b,c进行查找 .当最左侧字段是常量引用时，索引就十分有效。（电话簿中利用姓名查找人，姓和名分别是不同的列，知道姓电话簿有用，知道姓知道名电话簿有用，知道名不知道姓电话簿无用）

补充：
key_len：EXPLAIN执行计划中有一列 key_len用于表示本次查询中，所选择的索引长度有多少字节，通常我们可借此判断联合索引有多少列被选择了。

1、index Key：索引数据范围

• 下边界
  MySQL利用=、>=、> 来确定下边界（first key），利用最左原则，首先判断第一个索引键值在where条件中是否存在，如果存在，则判断比较符号，如果为(=,>=)中的一种，加入下边界的界定，然后继续判断下一个索引键，如果存在且是(>)，则将该键值加入到下边界的界定，停止匹配下一个索引键；如果不存在，直接停止下边界匹配。
• 上边界
  上边界（last key）和下边界（first key）类似，首先判断是否是否是(=,<=)中的一种，如果是，加入界定，继续下一个索引键值匹配，如果是(<)，加入界定，停止匹配

2、Index Filter ：用于过滤索引查询范围中不满足查询条件的记录

Index Filter的提取规则：同样从索引列的第一列开始，检查其在where条件中是否存在：若存在并且where条件仅为 =，则跳过第一列继续检查索引下一列，下一索引列采取与索引第一列同样的提取规则；若where条件为 >=、>、<、<= 其中的几种，则跳过索引第一列，将其余where条件中索引相关列全部加入到Index Filter之中；若索引第一列的where条件包含 =、>=、>、<、<= 之外的条件，则将此条件以及其余where条件中索引相关列全部加入到Index Filter之中；若第一列不包含查询条件，则将所有索引相关条件均加入到Index Filter之中。

以上index Key和Index Filter都是通过索引列来实现的，而Table Filter是针对非索引列

3、Table Filter ：无法使用索引过滤，使用表过滤

提取规则：所有不属于索引列的查询条件，均归为Table Filter之中。

where索引过程：

图片转载自：http://www.fordba.com/spend-10-min-to-understand-how-mysql-use-index.html

六、索引失效

1、在where后使用or，导致索引失效（尽量少用or）
2、使用like ，like查询是以%开头，以%结尾不会失效
3、不符合最左原则
4、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引
5、 使用in导致索引失效
6、使用mysql内部函数导致索引失效,可能会导致索引失效。
7、如果MySQL估计使用索引比全表扫描更慢，则不使用索引

七、索引Demo

CREATE TABLE table_name[col_name data type] [unique|fulltext][index|key][index_name](col_name[length])[asc|desc]

• unique|fulltext为可选参数，分别表示唯一索引、全文索引
• index和key为同义词，两者作用相同，用来指定创建索引
• col_name为需要创建索引的字段列，该列必须从数据表中该定义的多个列中选择
• index_name指定索引的名称，为可选参数，如果不指定，默认col_name为索引值
• length为可选参数，表示索引的长度，只有字符串类型的字段才能指定索引长度
• asc或desc指定升序或降序的索引值存储

• 创建数据库并添加数据

CREATE TABLE `students` (
  `stud_id` int(11) NOT NULL,
  `name` varchar(50) NOT NULL,
  `email` varchar(50) NOT NULL,
  `phone` varchar(30) NOT NULL,
  `create_date` date DEFAULT NULL,
  `content` text NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
INSERT INTO `students` (`stud_id`, `name`, `email`, `phone`, `create_date`, `content`) VALUES
(1, 'admin', '[e-mail]', '18729902095', '1983-06-25', 'i am robin'),
(2, 'root', '[e-mail]', '2', '1983-12-25', 'i am xiaoluo'),
(3, '110', '[e-mail]', '3dsad', '2017-04-28', 'i am lili');

1、创建普通索引

• 查看索引show INDEX from students
• 创建索引方式

1.直接创建:CREATE INDEX index_name ON student(name);
2、修改表结构方式创建索引：alter TABLE students ADD INDEX index_name2(name);
3、创建表的时候建立索引：添加：index index_name3(name)
创建后的索引：

查看是否通过索引能够获取数据：EXPLAIN SELECT name FROMstudentsWHERE name='admin'
通过索引获取数据：

-删除索引： DROP INDEX index_name ON table_name;
                    alter table表名drop index 索引名;

2、创建唯一索引（Index前边添加unique）

1、创建邮箱索引：

CREATE UNIQUE INDEX index_email on students(email);
ALTER TABLE students ADD UNIQUE INDEX index_mail2(email);
创建表的时候添加：UNIQUE index_name_unique(email);

3、创建主键索引

主键索引是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值。一般是在建表的时候同时创建主键索引：
1、创建邮箱索引：

ALTER TABLE students ADD PRIMARY KEY(stud_id);
创建表的时候添加：primary key(‘stud_id’)

4、创建全文索引

1、创建全文索引
创建表的时候添加：fulltext(content)
CREATE FULLTEXT INDEX index_content on students(content);
ALTER table students ADD FULLTEXT INDEX index_content2(content);
2、show index from students;

3、全文索引查询:

SELECT * FROM `students` WHERE MATCH(`content`) against('robin')

4、建立一个联合索引
添加另外一个全文索引：ALTER TABLE students ADD FULLTEXT INDEX email_content(email,content);
联合全文索引：SELECT * FROMstudentsWHERE MATCH(email,content) against('student robin')

八、引用博客

【1】实战demo：https://blog.csdn.net/u010648555/article/details/81102957
【2】B树与B+树：https://blog.csdn.net/endlu/article/details/51720299
【3】聚合索引与非聚合索引概念：https://blog.csdn.net/tongdanping/article/details/79878302
【4】InNoDB与MyISAM差别：https://www.cnblogs.com/y-rong/p/8110596.html
【5】组合索引：http://www.fordba.com/spend-10-min-to-understand-how-mysql-use-index.html
【6】Mysql如何利用索引，通过组合索引：http://hedengcheng.com/?p=577
图片：http://www.fordba.com/spend-10-min-to-understand-how-mysql-use-index.html
【7】索引使用规则;https://www.cnblogs.com/duanxz/p/5244703.html

一、为什么需要索引？（索引的优缺点）

1、索引产生的意义

没有索引行不行？答案是肯定的，可以不使用索引，在数据库中将数据整齐的排列在磁盘阵列中，当获取数据的时候只需要逐个搜索，并返回结果，但是 如果开发的应用有几百上千万甚至亿级别的数据，那么不深入了解索引的原理， 写出来程序就根本跑不动，光查一个数据库就得好几天，因此就需要索引，能够快速的查找的需要的数据。

2、索引的优缺点

• 优点

1、极大地加速了索引过程，减少IO次数
2、创建唯一索引，保证了数据库表中的唯一性
3、加速了表与表之间的连接
4、针对分组和排序检索时，能够显著减少查询查询中的分组和排序时间

• 缺点

1、索引表占据物理空间
2、数据表中的数据增加、修改、删除的同时需要去动态维护索引表，降低了数据的维护速度

二、索引的分类

1、唯一索引：表上一个字段或者多个字段的组合建立的索引，这些字段组合起来能够确定唯一，允许存在空值（只允许存在一条空值）
2、非唯一索引：表上一个字段或者多个字段的组合建立的索引，可以重复，不需要唯一
3、主键索引：（主索引）根据主键pk_clolum（length）建立索引，不允许重复，不允许空值；
4、聚合索引：表中记录的物理顺序与键值的索引顺序相同
5、非聚合索引：表中记录的物理顺序与键值的索引顺序无关
6、全文索引：在某个字段设置全文索引后，根据特定语法查找满足条件的字段;

1、全文搜索在 MySQL 中是一个 FULLTEXT 类型索引。FULLTEXT 索引在 MySQL 5.6 版本之后支持 InnoDB，而之前的版本只支持 MyISAM 表。
2、目前只有char、varchar，text 列上可以创建全文索引。
3、 like “value%” 可以使用索引，但是对于 like “%value%” 这样的方式，执行全表查询

7、普通索引：用表中的普通列构建的索引，没有任何限制
8、组合索引：用多个列组合 构建的索引，但是在使用过程中有诸多规则，遵循最左前缀原则，顺序至关重要
9、Hash索引（Memory存储引擎）是通过索引列的值计算出hashCode,之后在相应的物理位置存取索引列的值，由于hashCode的唯一性，因此Hash索引不能进行范围查找或者是顺序查找。

三、B树-数据库索引原理

转载自博客：https://blog.csdn.net/endlu/article/details/51720299
2019.8.26补充：https://www.cnblogs.com/nullzx/p/8729425.html（关于B树与b+树更通俗）

1、B树（平衡多路查找树）

特性：
（关键字个数 = 儿子节点个数-1、每一个关键字按照升序排序、非叶子结点也存储数据、根节点至少2个子女，非叶结点至少ceil(m/2)个子女）

• 树中每个结点最多含有m个孩子（m>=2）；
• 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
• 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
• 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
• 每个非终端结点中包含有n个关键字信息： (P1，K1，P2，K2，P3，…，Kn，Pn+1)。其中：
  a) Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
  b) Pi为指向子树根的接点，且指针P(i)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
  c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

2、B树插入删除

实例引用：https://www.cnblogs.com/nullzx/p/8729425.html

2.1、插入

1）根据要插入的key的值，找到叶子结点并插入。
2）判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
3）以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。(核心思想：找到中间值，提升为父节点，之后分裂为左右)

2.2、删除

1 ） 找到下一个记录，之后用下一个记录代替当前记录的位置
2 ） 当前节点个数大于ceil(m/2)-1,直接删除
3 ） 当前节点个数大于ceil(m/2)-1，跟兄弟节点借一个，前提是兄弟节点个数大于ceil(m/2)-1，兄弟节点借的节点上移，父节点ke下移
4 ）兄弟节点个数小于等于ceil(m/2)-1，父节点下移之后与兄弟节点合并

3、B+树

实例引用：https://www.cnblogs.com/nullzx/p/8729425.html

B+树特有：
1.有n棵子树的结点中含有n个关键字； (而B树是n棵子树有n-1个关键字)
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)
4.关键字按照从小到大的顺序排列

3.1 B+树插入

1. 根节点，直接插入就可以了
2. 叶子结点：由于在B+树中叶子结点实际保存了了数据，因此在插入B+树后如果当前节点小于m-1,直接插入；否则就将当前节点分解，左叶子结点包含前ceil(m/2)个，后ceil(m/2)+1记录到右节点，将ceil(m/2)记录的key进到父节点（父节为索引类型）
3. 索引节点：若当前结点key的个数小于等于m-1，则插入结束。否则，分裂左右，左前(m-1)/2个节点，右为后边的节点，之后选择（m-1）/2插入到父节点

3.2 B+树删除

4、B+树的优势

1、查找：B+树磁盘读写次数更低
因为B+树非叶子结点只是相当于一个索引，会将所有关键字具体信息都存储叶子结点，也就导致B+树能够存储更加多的关键字数量，构造的树更加矮胖，一次性读入内存的关键字数量增加，IO读写次数减少

1、 在索引查找的时候，B树的搜索方式是首先找到一个搜索下界，也就是满足条件的最低值，之后通过中序遍历的方式查找，而B+树在查找到搜索下界后，直接通过链指针开始查找关键字信息
2、范围查找：B树从二叉树的下限一直中序遍历，知道查找到二叉树的上线，而B+树知道二叉树下限后，直接链表查找
2、B+tree的查询效率更加稳定
由于非终结点不存储数据，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

5、B树与B+树的差别

引用自：https://blog.csdn.net/q936889811/article/details/79780307
1、B树的同一键不会出现多次，可能在叶子节点上也可能在非叶子节点上； b+树的键一定会出现在叶子节点上，同时也可能在非叶子节点上重复出现。
简单的说，b+树的非叶子节点存储的都是键值，键值对应的具体数据都存储在叶子节点上。
2、b数据的每个节点存储的是真是数据，会导致每个节点的存储的数据量变小，所以整个b树的高度会相对变高。随着数据量的变大，维护代价也增加； b+树的非叶子节点只存储的是键值，相对而言，一个非叶子节点存储的记录个数要比b树多的多。
3、b+树是横向扩展，随着数据增加，会变成一个矮胖子，b树是纵向扩展，最终树的高度越来越高（高瘦子）。
4、b树的查询效率与键在b树的位置有关系，在叶子及诶单的时候最大复杂度与b+树相同；b+树复杂度对某个建成的树是固定的。
5、 b树的键的位置不固定并且整个树结构中只出现一次，增删改查操作复杂度逐渐加；b+树中非叶子节点对于叶子节点来说就像一个索引，增删改的时候只要找到键值（索引）的位置，再一层层的向下找即可，只有在遇到一个节点存储满了会对b+树分裂。
6、 b树种所有的数据都只存储一份；b+树除存储了所有数据的叶子节点外，还有之存储键值数据的非叶子节点。所以，b+树比b树会多占存储空间，多占的空间就是b+树的非叶子节点的所有空间。

四、聚合索引与非聚合索引

聚合索引与非聚合索引是一种存储方式，而不是一种单独的索引类型

前提概念：
1、按照索引的键是否为主键来分为“主索引”和“辅助索引”，使用主键键值建立的索引称为“主索引”，其它的称为“辅助索引”
2、聚簇索引的辅助索引的叶子节点的data存储的是主键的值，主索引的叶子节点的data存储的是数据本身，也就是说数据和索引存储在一起，并且索引查询到的地方就是数据（data）本身，那么索引的顺序和数据本身的顺序就是相同的；
而非聚簇索引的主索引和辅助索引的叶子节点的data都是存储的数据的物理地址，也就是说索引和数据并不是存储在一起的，数据的顺序和索引的顺序并没有任何关系，也就是索引顺序与数据物理排列顺序无关。
3、两者相同点就是通过B+树结构来构造B树索引

1、聚合索引（InnoDB存储引擎需要）

定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。

1、选择B+树作为存储结构
2、聚合索引必须有主键，没有主键就会选择Unique key作为主键，没有Unique则会在系统内部生成rowid作为主键，因此主键不宜过长，使得辅助索引过大，主键如果不是单调的就会造成B+Tree频繁的分裂调整
3、在InnoDb上会选择自增字段作为主键，是为了维持B+树的分裂特性，顺序添加到当前索引的后续位置，当达到最大就会分裂产生新的页，也不需要移动原有的顺序
4、聚合索引主索引和辅助索引，主索引叶子结点存储键值对应的数据本身，辅助索引叶子结点存储主键键值
5、由于辅助索引存储的是主键键值，因此按照辅助索引搜索的时候需要检索两遍，第一遍找到对应的主键，第二遍在主索引到达叶子结点中找到数据

2、非聚合索引（MyIsam）

定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。

1、选择B+树作为存储结构
2、非聚合索引有主索引和辅助索引（两个索引几乎一样），但是主索引不允许为空，现在就需要考虑在索引分类中介绍的非聚合索引的概念，由于物理顺序与索引顺序不同，因此每一个叶子节点存储的是指向键值对应的数据的物理地址（数据记录的地址）
3、非聚簇索引的数据表和索引表是分开存储的
4、获取数据的方式是首先根据B+树获取索引，取出对应数据记录的地址，之后再去读取相应的数据记录
5、只有在MyISAM中才能使用FULLTEXT索引。(mysql5.6以后innoDB也支持全文索引)
6、辅助索引的意义：如果给出的查询条件不是主键，此时就使用辅助索引，并且使用辅助索引不需要使用主索引

1、使用聚合索引的场景：

• 某列包含小数目的不同值
• 排序和范围索引（主键递增）
  2、使用非聚合索引的场景：
• 某列包含大数目的不同值（因为在叶子节点不需要去保存数据，只需要保存地址）
• 频繁更新的列，因为非聚集索引添加记录时，不会引起数据顺序的重组

3、InNoDB与MyISAM异同

博客（自己还未阅读）：https://www.cnblogs.com/y-rong/p/8110596.html

1、InnoDB 支持事务，支持行级别锁定，支持 B-tree、Full-text （InNoDB从1.2.X版本开始支持全文搜索的技术）等索引，不支持 Hash 索引，但是给了又有一个特殊的解释：InnoDB存储引擎 是支持hash索引的，不过，我们必须启用，hash索引的创建由InnoDB存储引擎引擎自动优化创建，是数据库自身创建并使用，DBA（数据库管理员）无法干预；
2、MyISAM 不支持事务，支持表级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
3、Memory 不支持事务，支持表级别锁定，支持 B-tree、Hash 等索引，不支持 Full-text 索引；
4、MyISAM引擎不支持外键，InnoDB支持外键
5、MyISAM引擎的表在大量高并发的读写下会经常出现表损坏的情况
6、对于count()查询来说MyISAM更有优势，MyISAM直接通过计数器获取。InnoDB需要通过扫描全部数据，虽然InNoDB存储引擎是支持行级别所，InNoDB是行级别锁，是where对他主键是有效，非主键的都会锁全表的
7、MyISAM引擎的表的查询、更新、插入的效率要比InnoDB高，如果你的数据量是百万级别的，并且没有任何的事务处理，那么用MyISAM是性能最好的选择。并且MyISAM可以节省很多内存，因为MyISAM索引文件是与数据文件分开放置，并且索引是有压缩，内存使用率提高不少
8、平台承载的大部分项目是读多写少的项目，MyISAM读性能比InNoDB强很多

4、InNoDB存储引擎内幕略读

1、版本功能

2、关键特性

（1）插入缓存：正常插入自增ID速度非常快，但是如果使用UUID（防止注入式攻击，当我们使用主键自增的时候，需要删除一个东西的时候，一般都是id=？。这样的话我就可以在url中修改这个id的值，这样可能就被人删除了其他东西，UUID这个就是给主键id加上一层锁，使它不暴露给用户）者中随机插入（非连续）的值，此时需要离散的访问非聚集索引页，不是直接插入索引页，而是判断非索引也是否在缓冲池中，若在，则直接插入，若没在则放入Insert Buffer中，在Insert Buffer 中合并后插入到索引页，提高了插入性能

InsertBuffer使用条件

1. 索引是辅助索引
   2、索引不是唯一的

（2）两次写
避免在处理事务时候发生宕机，虽然说事务操作可以日志恢复，但是如果宕机的时候完全删除当前页，如果，doubleWrite，一部分为内存中doublewrite buffer ,大小为2M，另一部分物理磁盘表空间中连续的128个页。缓冲池的脏页刷新的时候，首先会刷新到doublewrite buffer中，之后才会写入到各个表空间文件，遇到宕机，只需要从共享空间doublewrite中找到该页的副本恢复，之后重做日志
（3）自适应hash索引
InNoDB会监控对表上的各索引页查询，如果观察到建立hash索引可以带来速度提升，则建立hash索引，自动根据访问评率和模式来自动为某些热点也建立索引
（4）异步io
AIO可以将多个IO请求进行IO Merge，当一个IO请求发出后，可以立即发出另一个IO请求，当所有IO请求发送完毕，等待IO操作完成

3、全文索引

使用倒排索引来实现，两种表现形式：
(1)inverted file index{单词，所在文档id}
(2)full inverted index{单词，（ 单词所在文档，在具体文档中的位置）}

4、锁

1、Recored Lock:当个行记录上锁
2、Gap Lock:间隙锁，锁定一个范围，但不包含记录本身
3.Next-Key Lock:锁定一个范围，并且锁定记录本身
4、InNoDB存储影青通过通过Next-Key Locking 来避免幻读问题

五、组合索引（覆盖索引）

基于多个字段创建的索引就是组合索引。

组合索引规则：
1、最左原则：索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种组合进行查找，但不支持 b,c进行查找 .当最左侧字段是常量引用时，索引就十分有效。（电话簿中利用姓名查找人，姓和名分别是不同的列，知道姓电话簿有用，知道姓知道名电话簿有用，知道名不知道姓电话簿无用）

补充：
key_len：EXPLAIN执行计划中有一列 key_len用于表示本次查询中，所选择的索引长度有多少字节，通常我们可借此判断联合索引有多少列被选择了。

1、index Key：索引数据范围

• 下边界
  MySQL利用=、>=、> 来确定下边界（first key），利用最左原则，首先判断第一个索引键值在where条件中是否存在，如果存在，则判断比较符号，如果为(=,>=)中的一种，加入下边界的界定，然后继续判断下一个索引键，如果存在且是(>)，则将该键值加入到下边界的界定，停止匹配下一个索引键；如果不存在，直接停止下边界匹配。
• 上边界
  上边界（last key）和下边界（first key）类似，首先判断是否是否是(=,<=)中的一种，如果是，加入界定，继续下一个索引键值匹配，如果是(<)，加入界定，停止匹配

2、Index Filter ：用于过滤索引查询范围中不满足查询条件的记录

Index Filter的提取规则：同样从索引列的第一列开始，检查其在where条件中是否存在：若存在并且where条件仅为 =，则跳过第一列继续检查索引下一列，下一索引列采取与索引第一列同样的提取规则；若where条件为 >=、>、<、<= 其中的几种，则跳过索引第一列，将其余where条件中索引相关列全部加入到Index Filter之中；若索引第一列的where条件包含 =、>=、>、<、<= 之外的条件，则将此条件以及其余where条件中索引相关列全部加入到Index Filter之中；若第一列不包含查询条件，则将所有索引相关条件均加入到Index Filter之中。

以上index Key和Index Filter都是通过索引列来实现的，而Table Filter是针对非索引列

3、Table Filter ：无法使用索引过滤，使用表过滤

提取规则：所有不属于索引列的查询条件，均归为Table Filter之中。

where索引过程：

图片转载自：http://www.fordba.com/spend-10-min-to-understand-how-mysql-use-index.html

六、索引失效

1、在where后使用or，导致索引失效（尽量少用or）
2、使用like ，like查询是以%开头，以%结尾不会失效
3、不符合最左原则
4、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引
5、 使用in导致索引失效
6、使用mysql内部函数导致索引失效,可能会导致索引失效。
7、如果MySQL估计使用索引比全表扫描更慢，则不使用索引

七、索引Demo

CREATE TABLE table_name[col_name data type] [unique|fulltext][index|key][index_name](col_name[length])[asc|desc]