入驻博客园的第一篇博客，希望能够将知识点解释清楚，有些地方可能有一些啰嗦，望见谅。（本文为转载，转载地址文末，自己加了一些结构上的调整）

一、几种树的介绍

　　首先介绍几种树的数据结构：二叉搜索树（BST）、平衡二叉树、B树、B+树

　　1.1 二叉搜索树

　　二叉搜索树具有以下性质：

　　（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；

　　（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；

　　（3）左、右子树也分别为二叉排序树；

　　（4）没有键值相等的节点。（往二叉搜索树中插入相同键值的元素会插入失败）

　　结构如图所示：

　　根据二叉搜索树的第一、二条性质，我们利用二分法可以快速查到某一个元素，查找的次数取决于二叉搜索树的深度，但是如果插入顺序不同可能会导致如下图所示的二叉查找树结构：

　　在上图的情况下，二叉查找树的查找效率退化为O(n)，所以又有了平衡二叉树。

　　1.2平衡二叉树

　　AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

　　由于本文主要是针对MySQL的索引原理，所以这里就是简单的提一下二叉搜索树和平衡二叉树的缺点，由此来引出B树和B+树。对于B树和B+树也仅是结合其性质来分析MySQL的索引原理。

　　1.3 B树

　　一颗M阶的B树的性质：

度：分为节点的度和树的度

节点的度：一个节点有几个孩子【一个结点含有的子结点的个数】

树的度：最大的节点的度为树的度

树的度也等于树的阶【B树中的结点的最大孩子数】

　　（1）m阶的B树，树中的每一个节点最多有m个孩子（以下图为例：假设最上面的节点的孩子最多，那么m为4，因为有4个箭头）

　　（2）每一个节点最多有m-1个key（以下图为例：最上面的节点有4-1=3个key）

　　（3）除根结点与叶子结点，其他结点的孩子数为[ceil(m/2),m]个。ceil函数表示上取整数

　　（4）所有叶节点具有相同的深度，等于树高h

　　（5）一个节点中的key从左到右非递减排列。

我们来看一下B树的结构和代码

/**
     * B树中的节点。
     */
    private static class BTreeNode<K, V> {
        /**
         * 节点的key-value的list，按键非降序存放
         */
        private List<Entry<K, V>> entries;
        /**
         * 内节点的子节点
         */
        private List<BTreeNode<K, V>> children;
        /**
         * 是否为叶子节点
         */
        private boolean leaf;
        /**
         * 键的比较函数对象
         */
        private Comparator<K> kComparator;

        private BTreeNode() {
            entries = new ArrayList<>();
            children = new ArrayList<>();
            leaf = false;
        }
        ...

　　在B树的节点中存在两个集合：一个是以Entry<K,V>为元素的List，一个是指向孩子指针的List；K存的是索引值，可以理解为被选择为索引的那个字段值，V是指的额外的数据。指向孩子的指针数比索引值的个数多1.由于B-树的性质，我们在利用其进行检索数据的时候是如下流程：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。B-Tree上查找算法的伪代码如下：

BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key)
    {
        if(node.key[i] == key) return node.data[i];
            if(node.key[i] > key) return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

　　关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为 $l o g_{d} ((N + 1) / 2)$

　　1.4B+树

　　B+树和B树有两点性质不同：　　

　　（1） B+树中每一个节点的指针数和key数一样

　　（2）内节点不存储data，只存储key；叶子节点不存储指针

　　我们来看一下B+数的结构：

　　可以看出来，B+树的内节点和叶子节点具有不同的存储空间，因此B+Tree中叶节点和内节点一般大小不同，这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。同时，一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。如下图所示：

　　在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。因为在计算机领域中有一个局部性原理。下面将介绍。

二、为什么要用B+树作为数据库索引

　 2.1 预备知识

　　一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

　　2.2 局部性原理　　

　　由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

　　2.3 B+树索引性能

　　到这里终于可以分析B-/+Tree索引的性能了。

　　上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为 $O (h) = O (l o g_{d} N)$

综上所述，用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

上文还说过，B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小：

$d_{m a x} = f l o o r (p a g e s i z e / (k e y s i z e + d a t a s i z e + p o i n t s i z e))$

floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

三、MySQL索引实现

　　3.1 MyISAM索引（非聚簇索引）

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

　　这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

　　同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

　　3.2 InnoDB索引（聚簇索引）

　　虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

　　上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

　　这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

四、MySQL索引优化策略

1、使用InnoDB，不建议使用过长的字段作为主键、因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大

2、非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择

3、请尽量在InnoDB上采用自增字段做主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页，这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：