本文转载自微信公众号《运维开发故事》，作者老郑。转载本文请联系运维开发故事公众号。概述索引是一种对数据库表中一个或多个列的值进行排序的结构，利用索引可以快速访问数据库表中的特定信息。索引数据结构二叉树二叉树（binarytree）是指树中节点的度数不大于2的有序树，是最简单也是最重要的树。二叉树的递归定义是：二叉树是一棵空树，或者是由一个根节点和两个不相交的左右子树组成的非空树，称为根；左子树和右子树也是一棵二叉树。对于数组{1,2,3,4,5}，数据结构会变成链表的特点：父节点下有两个子节点。右节点的数据大于左节点的数据。Binarytree.pngRed-blacktree红黑树是一种特殊类型的二叉树，是计算机科学中用于组织数据块（例如数字）的一种结构。如果二叉搜索树是红黑树，则它的任何子树都必须是红黑树。红黑树是平衡二叉搜索树的变体。它的左右子树的高度差可能大于1，所以红黑树不是严格意义上的平衡二叉树（AVL），但是平衡它的代价比较低。低，其平均统计性能强于AVL。由于每棵红黑树都是一棵二叉排序树，所以在搜索红黑树时，可以使用普通二叉排序树的搜索算法，搜索过程中不需要颜色信息。红黑树的数据结构如下：Red-blacktreedatastructure.png特点：红黑树是一种二叉搜索树，每个节点都有一个颜色属性，颜色为红色或黑色。节点为红色或黑色。根节点是黑色的。所有的叶子都是黑色的。（叶子是NIL节点）每个红色节点的两个孩子都是黑色的。（从每个叶子到根的所有路径上不能有两个连续的红色节点）从任何节点到每个叶子的所有路径都包含相同数量的黑色节点。这些约束强化了红黑树的一个关键属性：从根到叶子的最长可能路径不超过最短可能路径的两倍。结果是树大致平衡。因为插入、删除和查找值等操作的最坏情况时间需要与树的高度成正比，所以这个高度的理论上限允许红黑树在最坏情况下是高效的，不像普通的二叉搜索树。正是性质4导致路径上没有两个连续的红色节点来保证这个结果。最短的可能路径具有所有黑色节点，最长的可能路径具有交替的红色和黑色节点。由于根据属性5，所有最长路径都具有相同数量的黑色节点，这表明任何路径的长度都不会超过任何其他路径的两倍。因为红黑树是一种特殊的二叉搜索树，所以对红黑树的只读操作和普通的二叉搜索树是一样的。B-Tree的叶子节点深度相同，叶子节点的指针为空。所有元素都不重复。节点中的数据索引从左到右递增排列。B树数据结构。pngB+Tree非叶子节点不存储数据，只存储Index（冗余），可以存储更多的索引叶子节点，包括所有的索引字段，叶子节点通过指针链接，提高区间访问的性能（可以提高效率ofrangesearch)B+treedatastructure.pngFeatures关键字：节点内序，叶节点指针链接，非叶节点存储索引（冗余）查询mysql索引的数据页大小：mysql>showglobalstatuslike'Innodb_page_size';+-----------------+--------+|变量名|值|+------------------+------+|Innodb_page_size|16384|+----------------+------+为什么要设置16kb？hash对索引的key进行hash计算来定位数据存储的位置，当位置很多时，hash索引比B+树索引更高效。只能满足“=”，“in”不支持范围查询，存在hash冲突问题。hashdatastructure.pngindexInnoDB索引实现（聚合）表数据文件本身B+Tree组织的索引结构文件聚簇索引-叶子节点包含完整的数据记录为什么InnoDb表必须有主键，建议使用整数自增主键？如果没有设置索引，MySQL会选择一个唯一的数据列作为主键索引，如果找不到这样的列。将通过创建像rowid这样的隐藏列来实现。表数据文件按照B+Tree的数据结构维护，行的数据维护在叶子节点。所以必须有一个主键。整数类型更方便B+Tree排序。如果是自增，数据结构的存储速度更快，顺序存储不需要大量的树平衡操作。为什么非主键索引结构的叶子节点存放的是主键值？一致性，让主键索引先成功，再更新非主键索引关系，节省存储空间。主键索引示意图：InnoDBindeximplementation.png非主键索引示意图如果通过name=Alice查询：使用非主键索引进行查询，查询后得到信息(Alice,18).其实这里也是非聚集索引，然后查询回表，然后通过主键查询来做回表查询。两个数据文件：.frm主要存放表结构信息。ibd主要存储索引和数据MyISAM索引文件（非聚合）索引文件和数据文件是分离的（非聚合）MyISAM存储引擎index.png三个数据文件：.frm数据结构文件。myd文件主要是用来存放数据的。myi文件主要是存放索引信息。聚簇索引和非聚簇索引的特点：聚簇/非聚簇主要是索引文件是否和数据文件放在一起。在查询效率上，聚簇索引不会更高效地跨文件查询。Combined/compositeindex多个字段组织成一个公共索引combinedindex.png为什么要这样使用最左前缀的原则呢？索引数据是排序的，如果跳过该字段，则不能使用。例子：wherename='Jeff'andage=22--hitindexwhereage=30andpostatin='manager'--missindexwherepostation='dev'--missindex参考百度百科
