目录
首先介绍一款可以帮助理解数据结构的网站：Data Structure Visualization
是一种特殊的树，每个节点最多有两个子节点，值从左到右依次递增。
例如：当想查询值为11的数据时，如果没有索引要按顺序查找多次，有索引只查三次，加速了查询数据。同时树节点只能有两个节点，所有导致树很高，降低了查询速度
因为当值依次递增插入时，二叉树会退化成链表，对加快查询没有任何作用。
时间复杂度（代码执行的次数）：O(N)
特点：
- 每个节点只能是红色或黑色。
- 跟节点必须是黑色。
- 红色的节点，它的叶节点只能是黑色。
- 从任一节点到其叶子节点的所有路径都包含相同数目的黑色节点。
当数据插入时，红黑树通过旋转和变色来达到平衡。这样就弥补了二叉树退化成链表的尴尬
因为当值依次递增插入时树的高度会变得特别高。就例如上图查询0007只用3次，那查询70000呢？几乎要用30000次。效率会变得特别低。
时间复杂度为:O(log2N)
特点：
- 一个节点可以有多个元素
- 叶节点具有相同的深度，叶节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
虽然B树相对于红黑树，树的高度降低了，但是随着数据量的增多，树的高度还是会变得很高，效率会变得特别低。而且对范围查找也不方便。
特点：
- 非叶子节点不存储data，只存储索引（冗余），可以放多个索引。
- 叶子节点包含所有的索引字段
- 叶子节点用指针连接，提高区间访问性能（注意是单向指针。）
MySQL 使用的是B+树，但是不完全是。对原B+树做了一些改造，例如：
因为innodb表的索引结构是B+树，而B+树是基于索引来存储数据的。所有的数据全部保存在B+树的叶子节点上。
innodb引擎会查找并选择第一个没有null值的列，作为主键索引。如果没有，则会使用隐藏列作为主键。
优点：
节约空间
插入效率高（由于B+树遵循左小右大，所以自增插入数据总是在最右侧插入。而uuid则不一定，如果页16k已经写满了，那只能把页中的数据向后移，在空位中插入。频繁的移动分页会造成碎片，后续需要使用OPTIMIZE TABLE来进行碎片整理）
因为非主键索引存储主键值，是为了当数据变动时，不需要修改各非主键索引的值，只需修改主键索引叶子结点的数据即可。减少了重复操作，即提高性能。
1、为什么innodb和MyISAM引擎中不使用B树呢？
个人认为B树的页中即存储了指针也存储了数据，对于innodb和MyISAM引擎来说，每一页的存储文件都有大小限制的，这就造成了每页存储的信息大小也是受到限制的。
在数据存储过程中，数据所占空间大于指针所占空间的数量，所存储的指针数量较少。如果一张表想存储更多的数据，就必须增加页（存储文件）数，相当于增加节点的深度。在查询时遍历的次数增加和磁盘IO（打开存储文件）数据增加。
选用B+树的原因在于数据放在叶子节点上，子节点上有更多的空间存储指针数据，会很大程度上减少树的深度，从而减少对树的遍历次数和对磁盘的IO。例如：一个深度为5每个节点都有指针和数据的B树对比一个深度为2一层节点为指针一层节点为数据的B+树，从查询的的复杂度上来讲哪个更快？
2、什么是聚集索引、非聚集索引和回表？
聚集索引和非聚集索引从数据结构上讲都是由B+树实现的。
简单来说，聚集索引可以理解成主键索引，非聚集索引可以理解成除主键索引外所有自建的索引。那么问题来了，聚集索引和非聚集索引都是由B+树实现的，那为什么主键索引为什么比其它索引的查询速度要快呢？这里就要引出回表这个问题了。
什么是回表呢？
首先说一下聚集索引和非聚集索引的区别。聚集索引叶子节点存储的是数据，非聚集索引的叶子节点存储是的主键ID。通过非聚集索引查询出数据的主键，然后在使用聚集索引查询出最终的数据，这也就解释了什么是回表和为什么主键索引会比其它索引的查询速度要快。
延伸：
1、联合索引及索引最左匹配原则
联合索引相比于多个单独的索引，在一定程度上减少索引的存储空间和减少在查询索引时对磁盘的IO。
在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配。所以在联合索引查询时应该按照建立索引时的顺序书写查询条件。
例：联合索引union_index(a,b,c)
select * from table where a=1 (使用索引)
select * from table where a=1 and b=1 (使用索引)
select * from table where a=1 and b=1 and c=1 (使用索引)
select * from table where c=1 and b=1 (索引失效)
如详细了解，可阅读知乎《面试前必须要掌握的MySQL索引最左前缀匹配原则》，原文链接：https://zhuanlan.zhihu.com/p/144853595
2、字段和字段值上做计算和类型对索引的影响
一、在索引字段上使用计算类函数，会将字段转换成临时字段，从而无法对应索引，致使索引失效。
二、使用索引字段做查询条件时，‘=’左右两边值的类型保持一致，如果不一致什么导致索引字段类型转换变成临时字段。
三、在使用like的问题上尽量使用右%（like 'abc%'），在索引匹配时mysql遵照即最左优先。
四、索引字段不要使用NULL，因为NULL是一个特殊的值需要单独处理。单列索引不存储null值，复合索引不存储全为null的值。索引不能存储Null，所以对这列采用is null条件时，因为索引上根本没Null值，不能利用到索引，只能全表扫描。
3、为什么select字段往往使用索引字段比非索引字段要快
一、select字段尽量不要使用'*',在使用*作为输入字段时，引擎在查询时会先从字典表中查找出所有字段然后在匹配输出。
二、使用索引字段作为select输出字段速度快的主要原因在于，查询时引擎无需从磁上读取字段数据，直接从索引节点上返回数据。当然，如果列中存在非索引字段引擎不会从索引节点上返回数据，会从数据节点返回数据，这样索引列失效。
三、非索引字段一定比索引字段要慢么？事实上，如果查询还需要拿别的字段(如sex)，那么光查询索引就不够了，必须扫表。注意！在这里 mysql 查询引擎就会对两种情况做判断：
1). 从索引索引拿到对应id=12的主键id，然后根据id去表中拿结果。 2).直接全表扫描。
这里很多人有一个误区，认为1是好的，2是不好的。这是不对滴。全表扫描有时候会比先过索引在查表要快！
先说走索引的情况，比如说满足dept_id=12的主键id有1w个，而且均匀分布在不同的page里，那么mysql需要一个page一个page的把结果读取出来(random io)。需要磁盘io 1w次。 全表扫描的话，再比如全表有10w条记录，表文件为400m 大小(不少了吧)，那么因为是顺序读盘，一次最多读1m数据，那么只需要磁盘io 400次。
本节参考：
《mysql没有索引的字段_MySQL-mysql索引与select字段不是没关系吗？》
《MySQL在有索引列情况下select *的输出结果顺序》
4、为什么order by字段上使用索引字段更快
B+树的索引都是按照顺序存储的，所以在对结果处理时无需做过多的排序操作
5、多表关键查询时，为什么要小表驱动大表（小表在前，大表在后）
一、驱动表的定义
当进行多表连接查询时， [驱动表] 的定义为：指定了联接条件时，满足查询条件的记录行数少的表为[驱动表]
未指定联接条件时，行数少的表为[驱动表]（Important!）
忠告：如果你搞不清楚该让谁做驱动表、谁 join 谁，请让 MySQL 运行时自行判断
既然“未指定联接条件时，行数少的表为[驱动表]”了，而且你也对自己写出的复杂的 Nested Loop Join 不太有把握（如下面的实例所示），就别指定谁 left/right join 谁了，请交给 MySQL优化器 运行时决定吧。
如果您对自己特别有信心
memory [ˈmeməri]
MySQL 常用索引分为：普通索引、唯一索引、主键索引、组合索引、全文索引
关键字：Normal [ˈnɔːml]
普通索引是最基本的索引类型，唯一的任务是加快对数据的访问速度，没有任何限制。
默认会使用btree
// 1、直接创建索引
create index index_name on table(column(length));
// 常规创建
create index index_name on user(name);
// 针对字符串的前几个字符进行创建索引，节省空间，减少比较时间、解决排序问题
create index index_name on user(name(5));
//2、修改表结构的方式新增索引
alter table table_name add index index_name(column(length));
// 常规创建
alter table user add index index_name(name);
// 对字符串的前几个字符进行创建索引
alter table user add index index_name(name(10));
// 3、创建表的时候同时创建索引
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`name` char(20) CHARACTER NOT NULL ,
PRIMARY KEY (`id`),
INDEX index_name (name(length))
)
// 4、删除索引
drop index index_name on table;关键字：Unique [juˈniːk]
索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一
// 1、 创建索引
CREATE UNIQUE INDEX indexName ON mytable(username(length))
// 常规创建
create unique index index_name on user(name);
// 2、修改表结构
ALTER TABLE table_name ADD UNIQUE indexName(column(length))
// 常规创建
alter table user add unique index index_name(name);
// 3、创建表的时候直接指定
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`name` char(20) CHARACTER NOT NULL ,
PRIMARY KEY (`id`),
UNIQUE INDEX index_name (name(length))
)是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值。一般是在建表的时候同时创建主键索引
// 创建主键的时候自动创建主键索引
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` char(255) NOT NULL ,
PRIMARY KEY (`id`)
);主键索引和唯一索引的区别
主键是一种约束，唯一索引是一种索引，两者在本质上是不同的。
主键创建后一定包含一个唯一性索引，唯一性索引并不一定就是主键。
唯一性索引列允许空值，而主键列不允许为空值。
主键列在创建时，已经默认为空值 + 唯一索引了。
主键可以被其他表引用为外键，而唯一索引不能。
一个表最多只能创建一个主键，但可以创建多个唯一索引。
主键更适合那些不容易更改的唯一标识，如自动递增列、身份证号等。
在 RBO 模式下，主键的执行计划优先级要高于唯一索引。 两者可以提高查询的速度。
指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用组合索引时遵循最左前缀集合
ALTER TABLE `table` ADD INDEX name_city_age (name,city,age);全文索引主要用来查找文本中的关键字，而不是直接与索引中的值相比较。
fulltext索引跟其它索引大不相同，它更像是一个搜索引擎，而不是简单的- where语句的参数匹配。
fulltext索引配合match against操作使用，而不是一般的where语句加like。它可以在create table，alter table ，create index使用。
目前只有char、varchar，text 列上可以创建全文索引。
在数据量较大时候，现将数据放入一个没有全局索引的表中，然后再用CREATE index创建fulltext索引，要比先为一张表建立fulltext然后再将数据写入的速度快很多
// 创建表的适合添加全文索引
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`content` text CHARACTER NULL ,
PRIMARY KEY (`id`),
FULLTEXT (content)
);
// 修改表结构添加全文索引
ALTER TABLE article ADD FULLTEXT index_content(content)
// 直接创建索引
CREATE FULLTEXT INDEX index_content ON article(content)MySQL 索引方式分为：B-TREE 和 HASH。
1、B-TREE可理解为”排好序的快速查找结构”
每个叶子节点到根节点距离相等
所有被索引的列都是排过序的
适合范围查找、支持数据排序
2、HASH理论查询时间复杂度为O(1)
在磁盘随机存放数据
仅支持”=”,”IN”和”<=>”精确查询，不能使用范围查询
不支持排序
无法进行前缀索引
在任何时候都不能避免表扫描
检索效率高，索引的检索可以一次定位
只有Memory引擎支持显式的Hash索引
必须回行，通过索引拿到数据位置,必须回到表中取数据
1、like 以%开头，索引无效；
当like前缀没有%，后缀有%时，索引有效
2、or语句前后没有同时使用索引
当or左右查询字段只有一个是索引，该索引失效，只有当or左右查询字段均为索引时，才会生效
3、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来，否则不使用索引
数据类型出现隐式转化。如varchar不加单引号的话可能会自动转换为int型，使索引无效，产生全表扫描。
4、在索引字段上使用not，<>，!=
where中索引列有运算
不等于操作符是永远不会用到索引的，因此对它的处理只会产生全表扫描。 优化方法： key<>0 改为 key>0 or key<0。
5.联合索引失效情况
例如创建的索引是 key index （b,c,d）为联合索引，那么
有效情况： b || bc || bcd 这三种情况单独使用都是有效的
失效情况：bd || cd || d || c 这些情况下是无效的，组合列跨列使用都不能使索引生效
联合索引是最左匹配原则
在索引的排序上 , 是先按b排序 , 再按c排序 , 再按d排序
explain 关键字 查看SQL执行计划
- 页头：包含前后页的指针
- 页目录：包含数据区（分组）的最小id值，方便通过指针查询到数据
- 数据区：用于存放数据，指针依次向下。
比如：我要查询id为4的数据，需要从上到下查询4次。把数据区的数据分组，页目录存储每组数据最小的id值。那么我只需要通过目录3，查询2次即可。提高了查询效率。
当一页存满之后，数据会存放到下一页，通过双向指针连接，
如图：
当数据越存越多，最终多个页组成了链表
例如：我要查询1000，如果从第1页开始查询，一页一页遍历效率就太慢了（这就是全表扫描）
那怎么办？当然还是用类似页目录的方式了：如图：
到这里就可以大致看出来了，这个结构就是上面说的B+树。每一页即B+树的一个节点
在mysql目录的data目录下某个数据库名的文件夹下
myisam引擎：包含frm（结构文件）、MYD（data数据文件）、MYI(index索引文件)
innodb 引擎包含frm（结构文件）、idb（索引+数据文件）
innodb 索引文件和数据文件在一起的（聚集索引）
此处可以看出innodb比myisam引擎少一次磁盘io操作（不需要再去MYD文件取数据），可以说性能好一些。
例如创建的索引是 key index （b,c,d）为联合索引，那么
有效情况： b || bc || bcd 这三种情况单独使用都是有效的
失效情况：bd || cd || d || c 这些情况下是无效的，组合列跨列使用都不能使索引生效
联合索引是最左匹配原则
在索引的排序上 , 是先按b排序 , 再按c排序 , 再按d排序
表数据如下：
key 是主键 , b c d 创建了联合索引
生成的索引结构为:
先按照 b列排序，如果b列相同，继续按照c列排序，最后按照d列排序 结构如下
数据在联合索引 bcd 排序如下
