在mysql中，索引是存储引擎用于快速查找到目标记录的一种数据结构。常见的索引类型包含B树索引、哈希索引、空间索引(R-Tree)、全文索引等。
索引是在存储引擎层实现的，不同的存储引擎对索引的工作方式并不一样。
下面重点介绍B树索引以及innodb和myisam存储引擎。
选择B树的原因
读写磁盘代价最高的环节是寻道，按照顺序访问范围数据是很快的，这有两个原因：
- 顺序I/O不需要多次寻道，所以比随机I/O要快很多(特别是对于机械硬盘)。
- 如果服务器能够按需要顺序读取数据，那么就不需要额外的排序操作，并且goup by查询无需再做排序和将行按组进聚合计算了。
索引本身可能很大，不能全部放在内存，因此往往以索引文件的形式存储的磁盘上。这样一来，索引查找过程中就要产生磁盘I/O消耗。相对于内存存取，I/O存取的消耗要高几个数量级，设计索引时，其结构组织要尽量减少查找过程中磁盘I/O的存取次数。
B树是与红黑树类似的一颗平衡查找树，但在降低磁盘I/O操作次数方面更好一些，B树具有较低的深度，查找一个元素只需将很少节点从磁盘Load到内存，很快便能访问到要查找的数据。
B树介绍
B树
一棵B树T是具有如下性质的有根树(根为root[T]):
- 每个节点x有以下域：
- x.n，节点x包含的关键字个数。
- x.n keys本身,
以非降序排列,因此
。 - x.leaf，布尔值，如果x是叶节点，则为TRUE，若为内节点，则为FALSE
- 每个内节点x包含x.n+1个指向其子女的指针
,叶节点没有子女，故他们子女的指针域无定义。 - 如果ki为存储在节点x子节点内的关键字则:
- 每个叶节点具有相同的深度，即树的高度h
- 每个节点所包含的关键字个数x.n包含一个上界和下界，用一个固定的整数t>=2来表式；
- 每个非根的节点至少包含t-1个关键字。每个非根的内节点至少有t个子女，如果树是非空的，则根节点至少包含一个关键字。
- 每个节点至多包含2t-1个关键字，所以说一个内节点至少包含2t个子女，我们说一个节点是满的，如果这个节点恰好包含2t-1个关键字。
一棵高度为3的B树，它包含最小可能的关键字数，在每个节点x内显示的是n[x]
B+树
B+树是B树的一个变种，B+树比B树更适合实现外存储索引结构，MySQL存储引擎普遍使用B+Tree实现其索引结构。内节点只包含键值以及指向子节点的指针，数据存储在叶子节点，所有记录节点都是按照键值的大小顺序存放在同一层的叶节点中，各节点指针进行连接(双向链表)。
一棵高度为2的B+树
如图：所有记录都在叶节点中，井且是顺序存放的，如果我们从最左边的
叶节点开始顺序遍历，可以得到所有镗值的顺序排序15、10、15、20、25、30、50、55、60、 65、 75、 80、 85、 90
B+树内节点和叶节点的大小可以是不同的。
索引实现
存储引擎以不同的方式使用B+树，索引列是按照顺序组织的。B+树索引在数据库中有一个特点就是其高扇出性，因此数据库中B+树的高度一般都在2~3层，也就是说对于查找某一键值的行记录，最多只需要2到3次IO。
建立在B树结构的索引
B+树索引
数据库中B+树索引可以分为聚集索引(clustered index)和辅助聚集索引(secondary index),但不管是聚集还是非聚集的索引，其内部都是B+树的，即高度平衡的，叶节点存放着所有的数据。
聚集索引与非聚集索引不同的是，叶节点存放的是否是一整行的信息。
来看看InnodDB和MyISAM是如何存储下面这张表的：
|
1
2
3
4
5
6
|
Create Table layout_test(
col1 int not null,
col2 int not null,
primary key(col1),
key(col2) -- 二级索引
)
|
MyISAM引擎使用B+Tree作为索引结构，索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。叶节点每个项的数据域存放的是记录的地址，记录写入时按照插入的顺序存储在磁盘上。
MyISAM表layout_test的数据分布
MyISAM中主键索引和其它索引在结构上面没有什么不同，主键索引就是一个名为Primary的唯一非空索引。
MyISAM表layout_test的主键分布
MyISAM表layout_test的col2列索引分布
而在InnoDB中，主键就是聚集索引，表数据文件本身就是按B+Tree组织的一个索引结构，叶子节点包含了主键和行的全部数据，内节点页只包含了索引列主键。聚集索引中键值的逻辑顺序决定了表中相应行的物理顺序。InnoDB二级索引的叶子节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”,可知聚集索引就是按照表的主键构造的一棵B+树。
InnoDB表layout_test的主键分布
聚集索引的叶节点的每一个项包含了主键、事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。
InnoDB表layout_test的主键分布
InnoDB的二级索引和聚集索引很不相同。InnoDB二级索引的叶子节点存储的不是“行指针”，而是主键值，并以此作为指向“行的指针”。这样的策略减少了当前行移动或者数据页分裂时二级索引的维护工作。使用主键值当做索引指针会让二级索引占用更多的空间，换来的好处是，InnoDB在移动时无需更新二级索引中的这个“指针”。
从下图比较容易看出InnoDB和MyISAM保存数据和索引的区别。
聚集和非聚集对比图
聚集索引的优点
聚集索引的存储井不是物理上的连续，相反是逻辑上连续的，页内是连续的，页间通过双向链表链接。
聚集索引的另一十好处是，它对于主键的排序查找和范国查找速度非常快。
innodb的逻辑存储结构, 从InnoDB存储引擎的逻辑存储结构看，所有数据都被逻辑地存放在一个空间中，称之为表空间(tablespace)。表空间又由段（segment）、区（extent）、页（page）组成。页在一些文档中有时也称为（block），InnoDB存储引擎的逻辑存储结构大致如图:
image
- 可以把相关数据保存在一起，尤其是访问的数据聚集在一个页上，可以减少io次数；
- 数据访问更快。聚族索引将索引和数据保存在同一个B树中，因此从聚族索引中获取数据通常比在非聚族索引中查找更快。
- 使用覆盖索引扫描的查询可以直接使用节点中的主键值。
聚集索引的缺点
- 聚集数据最大限度的提高了I/O密集型应用的性能，但如果数据全部都放在内存中，则访问的顺序就没有那么重要了，聚集索引也就没有那么优势了；
- 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。但如果不是按照主键顺序加载数据，那么在加载完成后最好使用OPTIMIZE TABLE命令重新组织一下表。
- 更新聚集索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置。
- 基于聚集索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次分裂操作。页分裂会导致表占用更多的磁盘空间。
- 聚集索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。
- 二级索引（非聚集索引）可能比想象的要更大，因为在二级索引的叶子节点包含了引用行的主键列。
- 二级索引访问需要两次索引查找，而不是一次。
参考：