正文
什么是索引
在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。
索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值，然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快，可快速访问数据库表中的特定信息。
当表中有大量记录时，若要对表进行查询，第一种搜索信息方式是全表搜索，是将所有记录一一取出，和查询条件进行一一对比，然后返回满足条件的记录，这样做会消耗大量数据库系统时间，并造成大量磁盘I/O操作；第二种就是在表中建立索引，然后在索引中找到符合查询条件的索引值，最后通过保存在索引中的ROWID（相当于页码）快速找到表中对应的记录。——百度百科
索引的数据结构
数据结构有数组、链表、二叉树、平衡二叉树、红黑树、hash表、b-tree、b+tree等。但是常用作索引的有平衡二叉树、红黑树、hash表、b-tree、b+tree。下面分别介绍一下他们的特点。
二叉树和平衡二叉树
如上图第一个是二叉树，第二个是平衡二叉树，同样存储的是1-6的值。二叉树是一个树，其中每个节点都不能有多于两个节点。二叉树和平衡二叉树一样，都是左边的数比根节点的小，右边的数比根节点的大。第一个图展示了最差的一种二叉树。平衡二叉树是带有平衡条件的二叉树，必须保证树的深度是O(logN),而且左子树和右子树的高度最多相差1。二叉树理想的增删改查时间复杂度是O(logN),而最坏的情况是O(N)，而平衡二叉树的增删改查时间复杂度最坏和理想都是O(logN)。
红黑树（R-BTree）
上图是红黑树存储1-6的数据结构。从图上可以看出红黑树特点如下
每个节点是黑色或者红色。
根结点是黑色。
红黑树每个叶子节点都要是黑色的空节点，也就是说，叶子节点不存储数据。
如果一个节点是红色的，则它的子节点必须是黑色的。也就是说红黑树中两个相邻的节点不能同时为红色。
红黑树中每个节点，从该节点到达其可达叶子节点（null的节点）的所有路径，都要包含相同数目的黑色节点。
红黑树可以看成是一种特殊的平衡二叉树，所以他的增删改查的时间复杂度同平衡二叉树一样也是O(logN)。
hash
每次存入数据就会对key进行一次hash，计算出存储的位置。但是hash会出现hash碰撞，对于不同的key值可能计算出的结果是一样的。查找数据的时候先对key进行hash计算出所在位置，如果所在位置有多个，在进行key的比较。很多时候hash会比b+tree的效率高，因为key值hash后就能找到对应的位置。但是hash结构的数据不适合做范围查询。mysql是可以选择hash作为索引的。例如在查找历史订单的时候，以年份为查找条件，此时就可以考虑使用hash索引。hash的时间复杂度是O(1)。
B-tree
如上图是建立一个深度是3的B-tree存放1-6的值。如图可知B-tree的特点
叶节点具有相同的深度，叶节点的指针为空。
所有的元素不重复
所有的元素从左到右依次递增。
B-tree增删改查的时间复杂度是O(logN)。
B+tree
由图可知B+tree把所有的数据都放在叶子节点中，根节点和子节点存储的数据是叶子节点的地址。每个子节点的两端同样指向下一个子节点。同时叶子节点多了指针指向下一个节点。mysql底层索引也没有用这个b+tree，而是优化过的b+tree。
Mysql B+tree索引的数据结构
那么这样的数据结构特点是什么呢？
非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引。
叶子节点包含所有索引字段（查询的字段包含在联合索引内的好处）。
叶子节点用指针连接，提高区间访问的性能。
每个节点都是按照递增顺序排序，并且满足二叉树的左小右大的特点。
每个叶子节点的两端也保存相邻叶子节点的地址，就是说可以通过20，很快找到18所在的数据，这就是双向箭头的作用。
如何查找数据：
先从根节点开始查找，把根节点的数据放入到内存当中，然后采用类似二分法的方式查找。这算一次IO，但是因为在内存当中这次IO是非常快，真正耗费时间的是从根节点定位到子节点，再从子节点定位到叶子节点。例如查找56，可以直接在根节点找到，那么根节点的56所存储是叶子节点56所在的位置，就会定位到叶子节点56的位置，就可以找到数据。 例如查找20，在根节点中找不到，那么根节点15和56之间的空白处就是存储了子节点的地址，就会访问子节点继续按照这个模式查找。
我们知道树的高度影响着查找的性能，那么B+tree是如何满足mysql的呢？
索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动。盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页的大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。在mysql中根节点或者子节点称为数据页，每个数据页为16kb，通过
SHOW GLOBAL STATUS LIKE 'Innodb_page_size';
根据B+tree的结构图，假设主键key用bigint，bigint在mysql中占8（64位）个字节，空白处为子节点的磁盘地址，大约占6个字节。那么每个数据页大约能放(16384/(8+6))约等于1170个元素（一个key+一个指针），叶子节点特殊一些，叶子节点因为包含数据，就算它一条数据1kb，那么能存储16个元素(mysql存储的数据)。所以一个B+tree能存储1170*1170*16大约两千万左右的数据。也就是说千万级别的数据放在高度为3的树中，也就是说查找只需要3次IO。
为什么mysql使用B+tree而不是B-tree
B-tree根节点、子节点、和叶子节点有存储了数据。极大的占用了空间，按照上面B+tree的算法，B-tree每个数据页只能存放16个元素，那么如果存放千万级别数据，需要的高度大于3。
MySql索引
在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。
MyISAM索引实现
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
假设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。B+tree的叶子节点的只包含了部分数据，例如主键，那么这就是非聚集索引。例如除了主键索引外，其他的辅助索引，叶子节点的数据包含的是主键，然后根据这个主键进行回表，根据聚集索引获取到对应的数据。
InnoDB索引实现
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引（聚簇索引）。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），而且建议使用整形自增的列做主键，如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。为什么使用整形主键？因为整形相对于字符串来说比较大小的效率会高，因为在B+tree中不管是叶子节点还是根节点、子节点都是排好序的，同时整形存储需要的空间比字符串需要的空间要小。
为什么要使用自增主键？在B+tree中都是需要排好序的，如果选择自增，那么插入的时候只需要往后面插入数据就好。如果不是自增，那么数据插入后索引会进行维护，自动排好序，并且有可能做平衡转化。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：
辅助索引都存储了主键，通过索引查找到主键，在通过主键回表查询数据的过程，我们称之为回表，回表无疑降低了查询效率，这也就是为什么不建议使用select * 的原因之一。
参考
https://blog.csdn.net/admin522043032/article/details/120987864
