1.MySQL 索引
- 支持 B+树索引
- 全文索引
- 哈希索引（只有Memory引擎支持）
2.二叉树
- 二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
3.二叉查找树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
3.平衡二叉树
- 首先它是一颗二叉查找树，又称平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
- 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
4.B-Tree(B树)
- B树和B+树 都是有平衡二叉树演化而来，B代表平衡（Balance），但他们不是二叉树。
- 根节点（非叶子节点时）至少有2个子节点，左节点比根节点小，右节点比根节点大。
- 节点可以有多个元素，元素就是关键字（索引）。
- 子节点数比父节点元素数多1
- 所有叶子节点在同一层
- 叶子节点只有关键字不包含任何关键字相关表中的数据
- 所有节点都有卫星数据（Data域），即所有节点不仅包含了索引还包含了索引指向的表中数据。换句话说就是数据库表中的数据就存在B-树的节点中。
- 特点：
- 查询次数不比二叉树少，但是IO次数减少
- 对比IO时间内存中查询（同一节点多个元素之间查找）耗时可以忽略。
- 查看这篇关于B树文章
5.B+Tree
- 父节点中的元素在子节点中都有，并且是最大值。这样一来叶子节点中包含了所有索引数据。
- 所有叶子节点在同一层且只有叶子节点保存卫星数据，即表中的数据都在叶子节点中。
- 每个叶子节点都有指向下一个和上一个叶子节点的指针，叶子节点是一个双向链表结构。
- 特点：
- 由于节点不存放卫星数据所以一个节点可以存更多的索引，减少IO次数使B+树更加矮胖。
- 所有信息都存在叶子节点，每次都要查到叶子节点比较稳定，而B树最好情况是根节点查到，最坏情况是叶子节点查到所以不太稳定。
- 由于叶子节点时一个双向链表所以范围查询比较快，而B树没有链表要按某种顺序变量节点有增加了IO次数。
- 查看这篇关于B+树的文章
6.B树和B+树的使用
- 非关系型数据库如mongoDB 他们摆脱了关系模型，追求的是高性能，要求快速的拿出某一条数据，对范围查询需求不高，所以使用B树索引，查到之后就可以立刻拿到数据，因为数据就是存在索引处的。
- 关系型数据库如MySQL 范围查询就比B树快。
7.B+Tree类索引
- B+树索引主要分为2大类 聚集索引 和 非聚集索引
7.1 聚集索引
- 聚合索引根据主键自动生成的。所以索引的值决定了表中数据物理存放位置。
- 聚集索引只能有1个.
- 如果没有设置主键那么就会选取第一个不包含null值得唯一索引作为主键。
- 如果连唯一索引都没有那么会生成一个6字节的行号（rowid）作为主键。
- 根据主键构造B+树，叶子节点存放表数据。
- 聚集索引并不是物理上连续的而是逻辑上连续。
7.2 非聚集索引（普通索引，辅助索引）
- 普通索引是后期手动添加的，此时数据已经写入磁盘所以叶子节点不存数据。
- 其叶子节点不包含表数据而是存放指向表数据的指针。
- 普通索引就可以有多个。
7.3 主键索引和唯一索引
- 主键索引就是聚合索引，根据主键生成的索引。
- 唯一索引是约束条件的一种，唯一索引可以有多个。
7.4 覆盖索引
- 通过索引就可以查到所需数据，就不会再去表中查了，如查主键。查询语句要写出具体列，使用 * 不会使用覆盖索引。
- 覆盖索引无需设置，只要设置了索引，查询信息正好可以在索引中可以查到，他就不会去表中查。
7.5 前缀索引
- 对于保存很长的数据的字段如Text ,BLOB, 很长的VARCHAR 数据可以设置前缀索引。
- 但在分组和排序时前缀索引不会起作用，她也不会作为覆盖索引使用。
- 创建前缀索引： alter table table_name add key (column_name(prefix_length)) ，前缀长度按所需设置。
7.6 联合索引
- 表中2个或者2个以上的列创建的索引。
- 创建联合索引时索引列位置相当重要如以 （a b c d ）创建索引，如果没有查询条件没有a （最左前缀原则）那么是不会使用到联合索引的。其实这里创建了（a）,（a ,b），（a,b,c），（a,b,c,d）四个索引
- b and c 不会用到索引。
- a and c 只会用到索引a
- 联合索引的时候，区分度最高的字段在最左边。
- 联合索引还对第二个字段进行了排序，某些情况下可以减少一次排序。
8.哈希索引
-
将键值换算成哈希值，使用哈希索引只能进行等值查询，不能进行排序，模糊查找，范围查找。
- 哈希索引只需一次哈希所能算法就可以定位到对应位置。
- 只有HEAP/MEMORY引擎表才能显式支持哈希索引（NDB也支持，但这个不常用）。
- InnoDB引擎的自适应哈希索引，用户仅能开启该特性，不能对其进行人工干预。
9.走索引和不走索引
- 对于B+索引，当使用>、<、>=、<=、BETWEEN，in ，或者LIKE 'pattern' （其中'pattern'不以通配符开始）操作符时，可以使用索引。in 还和条件个数有关如果过多也不会使用索引
- 存在索引但不走索引的情况
- 复合索引未利用最左前缀原则。
- 不要在列上使用函数，这将导致索引失效而进行全表扫描。
- 负向条件查询不能使用索引如 !=、<>、not in、not exists、not like
- 强制转换可能导致索引失效而进行全表扫描如 varchar 型的 名称 = 123 ，这将int 转为 varchar 所以不会走索引，应该是 = ‘123’
- 如果引擎认为要扫描的数据过多也不会使用索引如 检索 'S%' 以S开头的数据过多，还不如进行全局扫描。
- 用or 分割开的条件如果有一个没有索引则整个都不会使用索引因为只要一次全表扫描就可以了。
- 索引优化博文