常见的索引结构有哈希表、有序数组、搜索树。
哈希表适合单个查询，范围查询性能很差。
有序数组所有查询都很好，但是新增修改成本很高，适合静态存储引擎。
搜索树在查询和修改方便较为均衡，一般时间复杂度为O（log n）。
当然树的结构有很多，熟知的二叉树，平衡二叉树，N叉树。
MySQL选用B+树的原因，是树的高度与调用磁盘的io的次数息息相关。相同的数据量，平衡二叉树的高度20，B+树的高度可能只有3。
主键索引
又称聚簇索引，MySQL存储表数据就在这里。叶子节点存的是整行数据。如果一张表创建时没有创建主键，InnoDB会默认创建一个主键维护索引。
非主键索引
又称非聚簇索引，叶子节点存的是主键值。通过非主键索引查询的，如果要查询索引上没有的字段，需要回到主键索引树再查一遍，简称回表。
如果不想回表，只需额外一个字段，可以使用覆盖索引。（这个需要权衡内存和性能，有一张6亿数据量的表，遍历查询30个非主键索引，耗时300ms，根据业务判断该sql只需要一个字段，那么组合一个覆盖索引，该查询耗时2ms）
自增主键在索引维护成本上会比其他主键低很多，所以尽量考虑自增主键。
原文：https://www.cnblogs.com/lanbitou-java/p/13623660.html