MySQL索引

所有的MySQL列类型都可以被索引，使用索引可以提高select操作性能，但是每个额外索引都要占用额外的磁盘空间，并降低写操作的性能。
MySQL有常见有四种索引，PRIMARY KEY（主键索引）、UNIQUE（唯一索引）、INDEX（普通索引）、FULLTEXT（全文索引）。它们均在在B+树中存储。
InnoDB底层有两种支持，B+树索引和Hash索引。Hash索引是自适应的，InnoDB引擎会根据表的使用情况自动为表生成Hash索引，不能人为干预是否在一张表中生成哈希索引。B+树并不能找到一个给定键值的具体行，能找到的只是数据行所在的页，然后数据库通过把页读入内存，再在内存中进行查找，最后得到查找的数据。
Hash索引只用于使用等式[= | <=>]比较，不能加速ORDER BY操作，不能确定在两个值之间大约有多少行，只能使用整个关键字搜索一行。B+树索引可以使用[> | < | >= | <= | BETWEEN | != | <> | LIKE]。
设计索引的几个简单原则：使用WHERE字句中出现的列或连接子句中指定的列，索引的基数越大效果越好，对字符串进行索引应该指定一个前缀长度，多列索引时可利用最左前缀，不要过度索引。
索引太多，也可能会使MySQL选择不到所要使用的最好索引，只保持所需的索引有利于查询优化。
要达到最好的性能，需要建立一颗最优二叉树，但是最优二叉树的建立和维护需要大量的操作，因此我们一般只需建立一颗平衡二叉树即可。平衡二叉树对于查询速度的确很快，但是维护一颗二叉树的代价是非常大的，通常需要1次或多次左旋和右旋来得到插入或更新后树的平衡性。
B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有节点都是按键值的大小顺序存放在同一层的叶子节点中，各叶子节点指针进行连接。
B+树的插入必须保证插入后叶子节点的记录依然排序，插入有3种情况，对应3种不同的插入算法，即(Leaf Page Full, Index Page Full) = (0, 0) || (1, 0) || (1, 1)，插入过程为了保持平衡可能需要大量的拆分页操作，为了减少拆分页操作，可以使用旋转，即将记录移到所在页的兄弟节点上。
B+树使用填充因子来控制树的删除操作，50%最填充因子可设的最小值，删除有3种情况，对应3种不同的删除算法，即(Leaf Page Below Fill Factor, Index Page Below Fill Factor) = (0, 0) || (1, 0) || (1, 1)。
一般在数据库系统或文件系统中使用的B+树结构都在经典B+树的基础上进行了优化，增加了顺序访问指针，做这个优化的目的是为了提高区间访问的性能。
B+树索引其本质就是B+树在数据库中的实现，B+树索引在数据库中的高度一般在2-3层，查找某一键值的行记录，最多需要2-3次磁盘IO，只需要20ms-30ms。
B+树索引可以分为聚集索引和辅助聚集索引（非聚集索引），两者不同的是，叶节点存放的是否是一整行的信息。聚集索引的叶节点存放着整张表的行记录数据，辅助聚集索引的叶节点存放着相应行记录的聚集索引的主键。
InnoDB存储引擎表是索引组织表，即表中的数据按照主键顺序存放，实际的数据页只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。聚集索引的存储是逻辑上的连续，即页通过双向链表连接，记录也是通过双向链表进行维护。因为聚集索引能够让我们在索引的叶节点上直接找到数据，所以查询优化器非常倾向采用聚集索引，并且使用聚集索引对于主键的排序查找和范围查找速度非常快。
辅助聚集索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助聚集索引。当通过辅助聚集索引来寻找数据时，InnoDB存储引擎会遍历辅助聚集索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。
B树与B+树结构主要有3点不同：1、两者每个节点指针数的上限不同（后者比前者多一个）；2、前者内节点和叶子节点都存储数据，后者只有叶子结点存储数据；3、前者往往对每个节点申请同等大小的空间，而后者叶节点和内节点一般大小不同。
不用红黑树用B+树与外存储器原理及计算机存取原理有关。1、红黑树深度一般比较大，意味着磁盘I/O次数相对较多；2、红黑树逻辑上很近的节点物理上可能很远，无法利用局部性（空间局部性，非时间局部性），意味着磁盘I/O效率相对较低。
不用B树而用B+树与两者结构有关。具体来说是因为B+树去掉了内节点的数据域，节点出度更大，出度越大性能越好。

参考：《深入浅出MySQL》、《MySQL技术内幕》、MySQL索引背后的数据结构及算法原理、从B 树、B+ 树、B* 树谈到R 树。