索引是对数据库表中一列或多列的值进行排序的数据结构。 表面层次来讲，索引就像一本书的目录，可以快速访问数据库表中的特点信息。 深层次来看，索引是帮助MySQL高效获取数据的排好序的数据结构，这个数据结构可以是平衡二叉树、红黑树、Hash表、B-Tree、B+Tree
演化：二叉树——红黑树——B-Tree——B+Tree 1、排序二叉树 假设有一表：t 有一sql语句：select * from t where t.col2=89 无索引时，进行全表遍历，直到符合条件，如图需要遍历6次。 以col2建立索引（假设该索引以二叉树去实现，实际大都以B树或B+树），则有： 那么根据排序二叉树“左小右大”性质，只需要两步就找到“89”的指针地址，再根据该指针到磁盘做一次IO，便可以找到想要的哪一行数据。 2、红黑树 排序二叉树的弊端：当以col1这类递增列为索引时，树的结构变成链表结构 这样一来就与全文索引无区别。 优化——红黑树：当单边结点超过3个，会自动平衡，则上述结构变成： 红黑树是一种含有红黑结点并能自动平衡的二叉查找树。性质： （1）、根结点和叶子结点都是黑色的 （2）、每个红色结点的两个结节点一定都是黑色 （3）、任意一结点到每个叶子结点的路径都包含数量相同的黑结点。 3、B-Tree 红黑树缺点，如上图，当持续有序递增加入结点数据时，会出现左空右满的情况，导致树的高度太高 优化：限制高度，扩展宽度。每个结点存储多个数据。每个又可以分叉，形成多叉平衡树。eg： 特性： （1）、叶结点具有相同的深度，叶结点指针为空 （2）、所有索引元素不重复 （3）、结点中的数据索引从左到右递增排序 当查找某个结点时，将该结点放到内存RAM中快速查找。 为什么不全部放到一个结点，一起放到RAM查找，因为内存是有限的。因此设置每个结点大小为16KB。 4、B+Tree（B-Tree的变种）：MySql的最终选择 特性： （1）、非叶子结点不存储数据（data），只存储索引（冗余），可以放更多的索引（每个结点16KB） （2）、叶子结点包含所有索引字段 （3）、叶子结点用指针连接，提高区间访问性能 叶子结点存放所有Data，并以链表形式呈现，体现两大特点：大数据存储、大规模查询（有序） 扩展——聚集索引和非聚集索引的区别： 聚集索引（主键、聚簇索引）：叶子结点存放整条记录（索引字段+数据），不需要回表。 非聚集索引（非主键、普通、二级索引）：叶子结点存放索引值和磁盘地址指针，需要回表。 详情见——存储引擎
