数据库常用索引类型及优缺点
（1）hash表：hash。
优点：查找复杂度o（1）
缺点：冲突，只能支持=和in操作，不支持范围查找（主要原因）
（2）二叉树及平衡二叉树红黑树：非常经典的索引数据结构，可以使用二分法进行查找，时间复杂度O(logn).但二叉树存在致命的缺陷，如下：
二叉树可能因为操作的原因退化为链表，例如插入一组有序数据生成的二叉树
如果为了应对上一条的问题引入平衡二叉树或者红黑树。这两个数据结构对比，红黑树是追求大致平衡的，从根到叶子节点的最长路径不多于最短路径的两倍，因此比平衡二叉树维护平衡的难度低。但是这两个数据结构依旧回避不了一个局限性。就是层高的增长，每一层在查找的时候都需要一次磁盘io，而磁盘io的速度极慢
（3）B树：
叶节点具有相同的深度，叶节点指针为空。索引不重复（对比B+树的索引冗余），节点中数据索引从左到右递增排列。
优点：比之二叉树系列的降低了树的高度，也就大量减少了磁盘io。
不足：范围查找十分麻烦，因为数据在节点上，并且数据在节点上本身页限制了一个节点的 度
（4）B+树：
- 结构类似B树，但是非叶子节点存储索引和指针，索引冗余。叶子节点有一个双向链表
- 优点：和b树差不多，但是非叶子节点不存数据，树高更低了
- 不足：暂时对比其它的算好了。
mysql的各种索引
普通索引：允许被索引的数据包含重复的值
唯一索引：可以保证数据记录的唯一性。主键索引是一种特殊的唯一索引。
联合索引：覆盖多个数据列。
全文索引：通过建立倒排索引，极大提升检索效率，解决判断字段是否包含的问题，是目前搜索引擎的关键技术。
补一下倒排索引的定义：从内容到id的索引。文章拆到关键字，然后关键字指向ID
实际应用
（1）myisam使用的是b+树，frm是表结构文件，MYD是是数据，MYI是索引，叶子节点存储数据所在磁盘位置
（2）innodb，frm是表结构，ibd数据和索引合并存储。如果是非主键索引，叶子节点存储主键。
索引相关的知识
（1）聚集索引和非聚集索引的区别（略），具体对比如下:
一般是聚集索引快一些，因为少了一次回表，较少了磁盘IO。
聚集索引对于范围查询的支持更好，因为数据的物理地址就是连续的
聚集索引适合用在排序的场合
聚集索引维护索引的成本比非聚集索引要高昂
（2）innodb必须建主键，且最好是自增的整型。不建主键，mysql会寻找一个不重样的列建立索引，如果找不到，会维护一个隐藏列，会浪费资源。至于整型，因为例如uuid，在索引比较的时候会更慢，而且uuid占用空间也比较大。并且由于uuid不是自增的，在插入的时候分裂的操作更难
（3）联合索引和最左前缀原则：（主体略，老生常谈了）但是在联合索引下，范围查找可能会全表扫描，例如因为有select *而导致不得不回表的情况，于其走索引加多次回表，不如直接在表里走扫描。而且一些不得不走全部索引的情况会走更小的联合索引表（因为联合索引表叶子节点内容更少。可能会需要扫描更少的页）
（4）插入即便没有顺序，查询得到的结果也是进行了排序的。插入的时候会进行排序，其实也就是B+树插入得到的结果是有序的。
（5）mysql在查询时，一次会载入一页数据，而不是一条，一方面减少磁盘io，一方面也是利用局部性原理
（6）order by因此索引失效的一个例子。对于有a,b,c,d,e的表，b,c,d是联合索引，select * rom xx order by b,c,d。虽然走联合索引可以不用排序，但是需要多次回表。而全表扫描再内存排序，会更快。
（7）数据转换对索引影响:select * from xx where a = “a”;如果a是数字类型，那么字符（串）都会被转化为0，除非字符串本身就数字。
（8）三星索引：1）一个查询相关的索引行时相邻的或者至少相距足够靠近 2）索引中的数据顺序和查找中的排列顺序一致 3）索引中的列包含了查询中需要的全部列 一般认为第三条最重要。