几个相关的概念
二分查找
在一个正序排序的数组中查找元素，所需查找的值与数组中间位置的值进行比较，若比中间值大，在后半部分中递归查找，若比中间值小，在前半部分递归查找
二叉查找树
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉查找树的定义：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有节点的值均小于它的根节点的值
若右子树不空，则右子树上所有节点的值均大于它的根节点的值
左、右子树也分别为二叉排序树
没有键值相等的节点
二叉查找树的搜索：
从根节点开始，若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树；
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功
平衡二叉树
在满足二叉树的定义基础上，满足左右两个子树的高度最大差1。
平衡二叉树有利于提高查找的性能。
B树
B-tree，B 即 Balanced，平衡的意思。中文名 B树，也有很多人译作 B-树。它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。
没有子节点的叫叶节点，没有父节点的叫根节点，其他为内部节点
一颗m阶的B树有如下特性：
如果根节点不是叶节点，那么它至少有两个子节点
每个节点最多有 m 个子节点
有 k 个子节点的非叶节点拥有
k − 1个键每一个非叶节点（除根节点）最少有
m/2个子节点所有的叶节点都在同一层
每个内部节点的键将节点的子树分开。例如，如果一个内部节点有3个子节点（子树），那么它就必须有两个键： a1 和 a2 。左边子树的所有值都必须小于 a1 ，中间子树的所有值都必须在 a1 和a2 之间，右边子树的所有值都必须大于 a2 。
B树在每一个节点中都存储值，所有的节点有着相同的结构
图为3阶B树
B树的搜索：
B树的搜索和二叉搜索树类似。从根节点开始，从上到下递归的遍历树。在每一层上，搜索的范围被减小到包含了搜索值的子树中。子树值的范围被它的父节点的键确定。
B+树
B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶结点中。
MySQL 的 BTREE 索引
MySQL中支持的索引方法有两种：
BTREE索引HASH索引
| 索引 | MyISAM 引擎 | InnoDB 引擎 | Memory 引擎 |
|---|---|---|---|
| BTREE 索引 | 支持 | 支持 | 支持 |
| HASH 索引 | 不支持 | 特殊支持 | 支持 |
其中 InnoDB 引擎支持的 HASH 索引是自适应的，InnoDB 引擎根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。
MySQL 的 BTREE 索引是使用 B+树 实现的，索引是存储引擎级别的概念，不同存储引擎中的实现方式是不同的。
聚集索引：按照每张表的主键构造一个 B+树，并且叶节点中存放着整张表的行记录数据。
辅助索引：也叫非聚集索引，叶节点不存储行数据。叶节点除了包含键值外，还包含一个书签，书签用来指示哪里可以找到与索引相对应的行数据。
| InnoDB | MyISAM | |
|---|---|---|
| 索引结构 | B+树 | B+树 |
| 主键 | 必须（如果没有显式指定，MySQL会自动选择或生成） | 非必须 |
| 主索引（主键上的索引） | 主索引使用的是聚集索引，索引文件就是数据文件，其叶节点的 data域 存放的有行数据 |
MyISAM 的主索引与辅助索引在结构上完全一样（没有主键则没有主索引） |
| 辅助索引（非聚集索引） | data域 的书签是对应的行数据的主键的值，通过主键的值在主索引中查找行数据 |
data域 的书签是一个行数据的标识符 |
| 索引长度 | 每个列的长度不能大于767 bytes；所有组成索引列的长度和不能大于3072 bytes | 每个列的长度不能大于1000 bytes，所有组成索引列的长度和不能大于1000 bytes |
BTREE 索引的使用
哪些字段使用索引可能加快查询
注意这里说的只是可能，并不是一定。
和其他表做连接的字段
查询条件中的字段
聚集函数
MIN()，MAX()中的字段order by和group by中的字段
联合索引
有多个字段需要使用索引，而 MySQL 查询只能使用一个索引，此时可以考虑使用多个字段建立联合索引，联合索引在使用时遵从最左匹配原则。
哪些场景不使用索引
表记录太少
数据重复率高且分布平均的字段（离散度低）
经常插入、删除、修改的表要减少索引
数据量大的列不应该建立索引，例如
TEXT类型，或者列长较大的VARCHARCHAR类型（假如前10个字符唯一，也可以只对前10个字符建立索引）。索引有长度限制，数据量特别大的字段也无法创建索引
何时索引会失效
联合索引未使用最左前缀，例如组合索引
（A，B），where B=b不会使用索引like左边使用通配符，where A like '%China'搜索一个索引而在另一个索引上做排序，如
where A=a order by B，只使用A上的索引，因为查询只使用一个索引（可以优化为A和B的联合索引）or可能会使索引失效。如果查询字段相同，也可以使用索引。例如where A=a1 or A=a2（生效），where A=a or B=b（失效）如果列类型是字符串，要使用引号。例如where A=’China’，否则索引失效（会进行类型转换）；
!=<>、not in等会使索引失效对索引列使用函数、运算符运算等会使索引失效。可以变换思路，将索引列与函数或运算表达式做对比
MySQL在执行查询之前，首先会通过优化器分析查询语句，当预估的返回行数超过一定数量，则MySQL有可能认为全表扫描更快，而不使用索引。范围查找，如果取出的数据行占表中大部分数据时，可能不会使用索引。
单纯的排序，而没有limit限制返回的行数，在表数据量大时可能不会使用索引
MySQL优化器预估的返回行数是不一定准确的，当预估的返回行数较大，实际的返回行数较小时，可以尝试强制使用索引，可能会更快select <字段> from <表名> force index(<强制使用的索引>)
如果一个索引在所有场景下均失效，则可以考虑移除此索引；如果既有失效的的场景，又有生效的场景，则可以考虑保留此索引