一、索引的本质
索引是帮助MySQL高效获取数据的排好序的数据结构
假设要查找地址为0x77的这一行记录
select * from t where t.col2 = 89如果不走索引，讲从第一行开始逐行查询，将查到的值与字段值相比对，要查很多次，效率很低（每查询一次就要与磁盘交互一次），走索引（图的右侧）之后，仅需查找两次。
但是MySQL的索引并没有采用二叉树作为存储结构，假设把col1作为索引字段，col1的特点是从小到大依次递增，就会出现下面的情形：
二叉树查找col1 = 6需要六次，和不走索引一样。
那采用红黑树作为索引结构可不可以呢？
红黑树查找col1 = 6需要三次
但是MySQL的索引结构也没有使用红黑树，因为红黑树有个问题：树的高度太高，还是需要相当多的磁盘I/O
对红黑树进行改进：既然红黑树的树高成了瓶颈，那就采用扁平化思想，让树的高度变矮，每一行存储更多元素，就变成了B树
但是MySQL并未采用B - Tree存储索引，而是继续改进，如下所示的B+ Tree
B+ Tree的特点：
- 把所有索引元素全部放到叶子节点
- 把非叶子节点的头元素作为冗余索引构建B+树，非叶子节点的
data元素跟着移到了叶子节点中 - 为每一个节点分配了一个大小：页(16kb)
- 叶子节点中的所有数据都是从左往右依次递增的。单看某一个小的二叉树，也有一个特点：叶节点的右半边
≥它的父节点，叶节点的左半边≤它的父节点 - 注意：每一个节点中的数据横向比较基本不花时间
- 叶节点上有双向链表，存放相邻文件的磁盘文件地址
现在再查找col1 = 6仅需两次
计算一下每个节点都放满，B+树可以存多少元素？
一般来说，主键采用int或bigint存储，以下计算假设采用bigint存储主键、采用主键索引维护整张表的数据、树高为3。
bigint大概占用8个byte，而一个节点的大小是16kb，空白区（即数据15和56之间的区域）存放的是磁盘地址指针，占用6个byte，因此第一行的节点可以存放的索引元素的个数为：
$$
\frac{16kb}{(8 + 6)byte} ≈ 1170(个)
$$
第二层的计算方式雷同，也能放1170个索引元素
叶子节点除了能放索引元素之外，还能放data元素，因此占用空间可能比较大，假设占用1kb，则叶子节点至多能放16个元素。
这样一来，三层树高的B+树可以存放的索引元素个数为：
$$
1170 × 1170 × 16 ≈ 2千多万
$$
此外，MySQL会把非叶子节点提前加载到内存中，但不是一直放在内存中，过一段时间就会把数据从内存中淘汰掉（为了节约内存），这就是MySQL的BufferPool缓存机制（缓存池）
二、MySQL的存储引擎
数据库中的表和文件夹中的文件是一一对应的关系
- MYISAM引擎：
- .frm：存储表结构
- .MYD：存储数据
- .MYI：存储索引
- InnoDB引擎：
- .frm：存储表结构
- .idb：存储数据及索引
MYISAM引擎查找数据的过程：
select * from t where t.col1 = 30先判断查找字段是否有索引，如果有索引则去.MYI文件中从根节点开始定位到索引元素，然后根据索引地址来到.MYD文件中查找对应的那一行数据
InnoDB存储引擎是把数据和索引设计在一个文件里的
聚集索引和非聚集索引
聚集索引：也叫聚簇索引，叶节点包含了整张表完整的数据记录（索引和数据放在一起）
非聚集索引：索引在.MYI文件中，数据在.MYD文件中
聚集索引比非聚集索引查询快，因为非聚集索引需要回表
非主键索引
比如将col3建为普通索引，一样的也是用B+树来构建，叶子节点存放的是主键
面试题1：为什么建议InnoDB表必须建主键？并且推荐使用整形的自增主键？
答：如果没有建主键，MySQL会帮我们找一个主键，从表里面逐列去找一个所有数据都不重样的列，也就是对那一列添加一个唯一索引，然后用这一列中的数据作为索引去组织表中的所有数据。如果每一列都有重复元素，那么MySQL会帮我们维护一个隐藏列，里面是自增的整形数据，用该隐藏列作为索引去组织表中的所有数据。时不时的插入索引会导致叶子节点分裂，分裂之后树还要平衡，效率不如自增主键。
补充：主键不建议使用UUDI，使用UUID比自增整形主键的效率低很多。因为UUID是字符串，而且是随机的。字符串比较大小需要逐位比较，而且每一位还要转换为ASCII码。
面试题2：B+树和B树的区别
答：有两个区别。一：b树没有维护双向指针，因此不支持范围查找，查找大于20的元素，在一个（叶子）节点中定位到20后，把同一节点上的指针拿出来，但是下一个节点就找不到了，又得回到根节点再从头遍历，找出其他节点，效率很低。二：B+树把非叶子节点上的元素都放到了叶子节点上，而非叶子节点仅存放索引元素。B树不放冗余索引，B+树放冗余索引，即所有数据都移到了叶子节点上。使用B树存放数据，由于非叶子节点上放了数据（占用空间），不可避免的会造成树的高度变高。即：
$$
16^n = 2千万
$$
$$
n >> 3
$$
也即：树的高度是由非叶子节点的分叉决定的，非叶子节点分叉越多，树的高度就越矮。
Hash索引
每插入一个索引，会先计算这个字段的哈希值，假设hash(Alice) = 2，就会把该哈希值放入2的桶中，接着把索引放到桶上的链表中，并存储索引所在行的磁盘文件地址，哈希碰撞时往后放
优点：在不发生哈希碰撞时，哪怕表中有1亿条数据，只需要一次哈希运算就能定位到元素
缺点：不支持范围查找
联合索引的底层存储结构（也是B+树）
