索引的基本概念
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是一种数据结构。
在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。
数据写入到mysql的时候，每行数据按照过来的先后顺序，顺序写入到磁盘。如果没有任何索引，我们查找某个值的时候，需要遍历整个磁盘进行查找，对于那些经常用于查找的列，我们可以为其创建索引，例如简单的二叉树。二叉树的节点的值是该列的值，同时有一个指针指向该值对应的磁盘的位置，通过二叉树很快定位到要查找的值，获取到磁盘上的对应的行的位置，从而很快取出这一行，比遍历整个磁盘要快得多。
B-Tree
B-Tree的节点是一个二元组[key, data]，key为记录的键值，data键key对应的数据。节点左右各有一个指针，分别指向下一层左右两个节点。
B-Tree查找的时候是基于二分查找的，所以当前高度的所有节点的key需要是有序的。当前节点的左右两个指针指向的节点，左指针指向的节点的key小于当前节点，右指针指向的节点的key大于当前节点。
B-tree的重要概念：
- d（B-Tree的度）：度会对约束节点的key和指针的数量，每个非叶子结点由n-1个key和n个指针组成，其中d<=n<=2d；每个叶子结点至少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶结点的指针均为NULL；
- h（B-Tree的高）：所有叶结点都在同一层，深度等于树高h；
B-tree需要满足的条件：
为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：
- d>=2，即B-Tree的度；
- h为B-Tree的高；
- 每个非叶子结点由n-1个key和n个指针组成，其中d<=n<=2d；
- 每个叶子结点至少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶结点的指针均为NULL；
- 所有叶结点都在同一层，深度等于树高h；
- key和指针相互间隔，结点两端是指针；
- 一个结点中的key从左至右非递减排列；
- 如果某个指针在结点node最左边且不为null，则其指向结点的所有key小于v(key1)，其中v(key1)为node的第一个key的值。
- 如果某个指针在结点node最右边且不为null，则其指向结点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。
- 如果某个指针在结点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向结点的所有key小于v(keyi+1)且大于v(keyi)。
关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找结点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。简单理解就是树的高度和key的数量成对数的关系，量很大的key生成的树的深度也很浅，查询很快。
根据B-Tree的定义，可知检索一次最多需要访问h个结点。B-Tree中一次检索最多需要h-1次I/O（根结点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，度d是非常大的数字，通常超过100，因此h非常小。
B树是为磁盘存储而专门设计的一类平衡搜索树，B树的高度仅随着它所包含的节点数按对数增长，因为单个节点可以包含多个key，所以对数的底数可以比较大，实际应用中一般是50~2000，给个直观的数字，一棵度为1001、高度为2（不包含根节点）的B树，可以存储超过10亿个key！由于每个节点内部的key是有序的，所以在每个节点内部可以通过二分查找快速找到指向下个节点的指针，最后定位到叶子节点中对应的key，上面所说的10亿个key的三层的B树只需要三次查找就可以定位到key对应的记录的位置，速度是相当快的。
索引的存储
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。
磁盘的操作：
- 寻道：读写头连接到一个传动臂的一端。通过沿着半径轴前后移动传动臂，驱动器可以将读写头定位到任何磁道上（盘片不动，磁头动）
- 旋转：一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到位的值，也可以修改值（磁头不动，盘片动）
磁盘的存储概念：
- 扇区：每个同心环叫做一个扇区，扇区是磁盘的最小存储单元。当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间；然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
- 页：由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。预读可以提高I/O效率。预读的长度一般为页（page：计算机管理存储器的逻辑块-通常为4k）的整倍数. 主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中。
这样做的理论依据是计算机科学中著名的局部性原理：
1 | 当一个数据被用到时，其附近的数据也通常会马上被使用。 |
也就是说，程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在B+Tree每次新建一个节点的同时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
mysql的索引引擎
MyISAM & InnoDB 都使用B+Tree索引结构。但是底层索引存储不同，MyISAM 采用非聚簇索引，而InnoDB采用聚簇索引。
- 聚簇索引： 索引 和 数据文件为同一个文件。
- 非聚簇索引： 索引 和 数据文件分开的索引。
MyISAM
MyISAM索引按照B+Tree搜索，如果指定的Key存在，则取出其data域的值，然后以data域值-数据指针地址去读取相应数据记录。辅助索引和主索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。MyISAM索引树如下：
InnoDB
InnoDB优势：
- 高扩展性
- 充分发挥硬件性能
- Crash Safe
- 支持事务
- 可以在线热备份
InnoDB物理存储结构如下图：
InnoDB以表空间Tablespace(idb文件)结构进行组织，每个Tablespace 包含多个Segment段，每个段(分为2种段：叶子节点Segment&非叶子节点Segment)， 一个Segment段包含多个Extent，一个Extent占用1M空间包含64个Page（每个Page 16k），InnoDB B+Tree 一个逻辑节点就分配一个物理Page,一个节点一次IO操作。一个Page里包含很多有序数据Row行数据，Row行数据中包含Filed属性数据等信息。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。