索引的用处
索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。
官方对索引的定义：索引（index）是帮助高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构
用平衡二叉树？
数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。
最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找、平衡二叉树查找。
从理论上来说，似乎没有什么问题，但是如果仔细考虑我们对数据库的使用，会发现，
第一，我们一个表中的数据存储量会很大，数据量在万以内的我们都认为这是个小数据量表，一般的表数据量都以十万计，百万级别的表也不在少数，用二叉树来索引的话，这个树就会是个很高很瘦的树，层次很深，查找的次数会有几十次次之多；
①6条数据时的平衡二叉树是三层；②20条数据时的平衡二叉树是6层；
第二，因为数据量很大，相应的索引也会很大，不可能全部存储在内存中，数据库是做数据持久化的地方，索引文件不可能永驻内存，因此索引往往以索引文件的形式存储的磁盘上，
这样。索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。
这样磁盘存取也成为我们在设计索引时必须要考虑的主要因素之一。
磁盘存取原理
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。
当需要从磁盘读取数据时，为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为4k的整数倍(这个4K大小的数据块，称为页)。
B树(平衡多路查找树, B-树)
有没有一种既可以避免二叉树这种搜寻深度过深，又可以充分利用磁盘预读原理的数据结构呢。这个就是B树了。B树中一个节点可以允许有多个子节点，在实际使用时，一个B树节点的实际大小一般设为一个4K大小的页，这样每个节点只需要一次I/O就可以完全载入。同时，B树的每个节点有多个key，并且以升序排列
①允许3个子节点的B树，存放6条数据时；②允许7个子节点的B树，存放27条数据时；
结论：B树允许的子节点的个数越多，相同数据下，相对于二叉树，这棵树就越矮，查找指定记录搜寻的次数就越少
B+树
MySQl等数据库系统实际使用的是B+树，B+树是B-树的变体，定义基本与B-树相同，不同点：
①所有的非叶子节点上不包含数据信息，因此在内存页中能够存放更多的key，所有数据都保存在叶子节点中；
②叶子节点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。
MySql索引的实现
MyISAM
使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集”的。
InnoDB
也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
①第一个重大区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
②而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
③叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
———————————————-后续补充索引的设计与优化