索引就是一种快速检索的、排好序的数据机构。
本质：数据结构+算法
类别及数据结构
Hash表
能够快速查找O(1)，但是会发生hash冲突，且不支持范围查询、排序，只支持=、in。
二叉树
一颗相对平衡的有序二叉树，可进行插入、查找、删除。O(logn)
缺点：存在致命的倾斜性问题，如
果数据往大从小插入，或是由小从大插入 ，都会导致倾斜。即最大化查询。
红黑树
相对二叉树更加平衡，查询的次数也相对可以接受，但是红黑树自旋后还是会发生倾斜性的问题。
B-Tree
叶节点具有相同的深度，叶节点的指针为空；
所有索引元素不重复；
节点中的数据索引从左到右递增排列
B+Tree(B-Tree加强)
非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
叶子节点包含所有索引字段
每个节点都有指定的degree，相邻节点靠指针关联(链表)，值存在叶子节点上。
引擎下实现
mysql索引时如何存储的： 引擎是表级别的，持久的，是一个文件，存储在磁盘上
MyISAM（非聚集）
不支持事务、也不支持外键，优势是访问速度快，对事务完整性没有 要求或者以select，insert为主的应用基本上可 以用这个引擎来创建表，支持FULLTEXT索引，并且只为CHAR、VARCHAR和TEXT列。
frm：创建表的文件
myd：表的数据文件
myi：表的索引文件，存的地址
索引查找： 以id为索引的B+tree（myi文件），得到id对应的物理地址(叶子结点上)，然后再去myd文件查找对应的数据。以字符型，中文的为索引，存的就是ASCII，重复度很高不建议用索引(男女)，磁盘IO还是会发生，浪费资源。
InnoDB（聚集）
该存储引擎提供了具有提交、回滚和崩溃恢复能力的事务安全。但是对比MyISAM引擎，写的处理效率会差一些，并
且会占用更多的磁盘空间以保留数据和索引。
InnoDB存储引擎的特点：支持自动增长列，支持外键约束
聚集索引 ：插入的时候会按主键排序
frm：创建表的文件
ibd：索引+数据
索引查找:以id为索引的B+tree（myi文件），叶子节点存的是id+数据（如1，a）
以字符型，中文的(username)为索引，叶子节点存的是id；降低存储空间，减少索引创建
叶子结点每页默认是16k数据。
为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
答：mysql在建表时，会主动寻找某一个没有相同数据的列，没有则会创建一个列，相当于rowid，会浪费时间，而且在索引查找的时候，B+Tree存的是记录的ID，如果是rowid不利于查找。
自增主键，涉及了B+Tree数叶子结点的裂变，当叶子结点存不了数据时，会新开一个节点，这时候使用自增id，效率更高，如果用uuid等，还需要每次都去比较，而且uuid字符比较可能会消耗更多的时间。
为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
答：非主键索引，比如二级索引，字符列name加的索引，叶子结点上key是name值，value是对应的记录ID，因为存的是ID，可以进行回表查询操作，更精确地查找记录，保证数据的一致性。而且不用像唯一索引一样去维护整个数据，可以节省内存空间。（没新增一个索引就多一个B+Tree的结构）
联合索引
多个列进行的组合索引，查询需符合最左前缀原则。
例：现有一个索引 a_b_c -->以下组合可用 ： a,b,c ; a,b ; a 三种情况
底层数据结构：
也是B+Tree实现，不过非叶子结点存的是组合的值，如name、age，Alice 12， Bob 14，先对name进行排序，再对age进行排序。