浅谈 MySQL 索引的实现
索引本质上是一种数据结构，能够帮助数据库高效地获取数据。我们都知道 MySQL 数据库使用 B+树作为索引的实现，那么具体是如何实现的呢，下面进行详细的探究。
索引
这是一种可能的索引方式，左边是数据表，共有两列七条记录，最左侧是数据记录的物理地址。为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树（实际环境中不会使用二叉查找树作为索引结构，这里只是简单演示），每个节点包含索引键和一个指向对应数据记录的物理地址的指针。
MyISAM 引擎的索引实现
在 MySQL 5.1 以前，MyISAM 是默认的存储引擎，每个 MyISAM 在磁盘上存储成三个文件，每个文件的名称均以表的名称开始，扩展字段指出文件类型，其中 .frm 文件存储表的定义，.MYD（MYData）文件存储表的数据，.MYI（MYIndex）文件存储表的索引。
MyISAM 引擎使用 B+树作为索引结构，叶子节点的 data 域存放的是数据记录的地址。
这里的表有三列，假如 Col1 为主键，则上图就是一个通过主键建立的索引。在 MyISAM 中，主键索引和非聚集索引（辅助索引）在结构上没有任何区别，只是主键索引要求 key 是唯一的，而辅助索引的 key 可以重复。
因为 MyISAM 中没有聚集索引，所以主键的索引我们就叫它主键索引，与普通的索引（辅助索引）相区分。MyISAM 中的表可以没有主键。
InnoDB 引擎的索引实现
在 MySQL 5.1 以后，InnoDB 是默认的存储引擎，在创建 InnoDB 表时，MySQL 会在数据目录下的数据库目录中创建一个 .frm 文件存储表的定义，还会创建一个 .ibd 的表空间文件，存储表的索引和数据。
InnoDB 引擎同样使用 B+树作为索引结构，但是与 MyISAM 引擎不同的是，它的主键索引是聚集索引，叶子节点存储的是完整的数据记录，它的辅助索引（非聚集索引）中，叶子节点存储的是主键的值而不是地址值。
上图是 InnoDB 主键索引的结构，叶子节点存储的是完整的数据记录。如果数据表没有显式指定主键同时表中也不存在合适的 unique 索引，则 InnoDB 会自动为该表生成一个隐藏的列作为主键，该列是一个 6 字节的长整型字段。
上图在 Col2 上添加了索引，这就是 InnoDB 辅助索引的结构，叶子节点存储的是主键的值。辅助索引使用主键值来实现类似指针的效果，虽然会让辅助索引占用更多的空间，但是换来的好处就是当移动行时无需更新辅助索引中的这个“指针”。
使用辅助索引搜索时需要检索两遍索引：首先检索辅助索引获得主键，然后通过主键到主键索引中检索获得记录。由于 InnoDB 中所有的辅助索引都会引用主键，所以过长的主键会令辅助索引变得很大，这也是为什么推荐使用自增主键而不是业务相关的其他随机字符串作为主键的一个原因。同时，推荐使用单调递增的字段作为主键可以避免在插入新记录时数据文件为了维持 B+树的特性而频繁地分裂调整。
主键的选择
在使用 InnoDB 时，如果没有特殊的原因，推荐使用与业务无关的自增字段作为主键。因为 InnoDB 的索引是聚集索引，这就要求同一个叶子节点内的各条数据记录按照主键的顺序存放。每当有一条新的记录插入时，MySQL 会根据其主键将其插入到适当的节点和位置，如果页面达到装载因子（InnoDB 默认为 15/16），则会开辟一个新的节点（页）。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满后，自动开辟一个新的页。这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时不需要移动已有的数据，同时索引的维护开销很小，因此效率很高。
如果使用非自增主键，由于每次插入主键的值近似于随机，每次新纪录都要插入到现有索引页中间的某个位置。此时 MySQL 不得不为了新纪录插入到合适的位置而移动数据，甚至目标页面可能已经被写回到磁盘中而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁地移动、分页操作造成了大量的碎片，得到的索引结构不够紧凑。
索引树高度计算
假如一张 InnoDB 表有 3000 万条记录，使用一列占用 8 个字节的字段建立索引，索引树的高度是多少？
要计算索引树的高度，需要先知道每个节点的大小。我们知道，现代的数据库一般会利用磁盘的预读机制，每个索引节点的大小一般是操作系统内存页的整数倍，操作系统页的大小一般是 4K，而 InnoDB 的页大小默认为 16K。接下来需要知道一个节点能够存放多少个键。非聚集索引中，节点包含键值、指针和主键数据，根据 pagesize/(keysize + datasize + pointsize) 公式我们可以得到键的数量，假设主键字段的大小为 6 个字节，指针大小为 4 个字节，则 16K/(8 byte + 6 byte + 4 byte) $\approx$ 910。然后根据树的高度计算公式求出树高大约为 $log(2^{10},2^{25})\approx$ 2.5。