索引的概念解释起来很简单，新华字典你要查一个字，字典前面的目录就是一个索引。索引的目的就是加速查找的操作，减少全表扫描造成的服务器开销。
索引有很多种，综合起来大概有如下这些： - B-Tree - Hash - R-Tree - 全文索引
大多数索引都是这个类型，或者B+Tree(InnoDB引擎就是这个)。 B树和B+树实际上是数据结构，因此要介绍这种类型的索引，首先需要了解这种数据结构。
B树数据结构介绍： 有关B树的数据结构的详细介绍，可以看这篇文章，作者将大量精品的教程文章托管在github上，非常厉害(还出书了呢)。 篇幅有限，我这里就根据上面这篇文章的内容写一个简化版。
首先，树这种结构，应该算是计算机数据结构里比较复杂的一种。顾名思义，它的结构像一颗树(倒过来的树……)，由一个根节点向下生长，一个根节点有多个子节点，每个子节点又有很多子节点，那些没有子节点的子节点就被称为叶子节点。 事实上，这种结构在我们日常使用中是很常见的，仔细想想就会发现，我们使用的操作系统正是使用树这种结构来管理文件的，打开我们的资源管理器，你就能看到一颗树。 但是要想把树这种结构用在索引里，可不是简单的普通的树就能搞定的。如何能够以最少的开销获得最快速的查找？在普通的树里查找会比链表或者数组快吗？ 于是计算机领域的科学家们发明了各种各样的树：二叉查找树、平衡二叉查找树、红黑树以及接下来要讲的B树。 B树全名是平衡多路查找树（b是英文单词balanced，平衡的）。 由名字可以知道下面这些事实： - B树是一颗平衡树。什么是平衡树？就是左子树和右子树的高度差不超过1，且左右子树的子树们也满足这个条件。这样说可能太抽象了，你还是在脑海里想象一颗真正的树吧，然后想象这棵树左半边和右半边发育的程度差不多，那它就是一颗平衡树。如果这棵树左边阳光比较充足，它左半边生长的特别茂盛高大，右半边生长的很慢很稀疏，你懂得，这是一颗不平衡的树。 - B树是一颗多叉树。和二叉树相对，B树是多叉的。二叉树要求树中所有的节点子节点都不能超过2。B树没有这个限制。
B树结构之所以被选中用做索引，是因为索引也是很大的，是需要放在硬盘上的，而现在大多数的机械硬盘和内存比起来都是非常慢的，要在一排碟片中找到想要的数据，磁头需要寻道移动到合适的位置，结构就像你们在电影里看到的很多欧美老式留声机一样。如果数据不能合理地归放，查找一次数据就会造成磁头频繁地在碟片上方移动，移动耗费的时间代价是非常大的。 后文可以看到，B树这种结构降低了磁头移动的次数，从而显著降低查找时间。
废话了这么多，让我们直观地看一下B树结构： {% asset_img btree.jpg B-Tree %} 这是一棵4阶的B树。阶的定义就是这个树每个节点至多拥有的子节点数，如果是4阶则至多拥有4个子节点。阶必须大于等于2，否则没意义。 然后我们罗列一下如下B树定义： - 根节点至少有两个子节点，或者整个树只有根节点本身。 - 这是4阶的树，因此每个节点至多有4个子节点。如果是M阶，那就至多M个子节点。 - 每个节点至少有M/2个子节点，M/2向上取整，根节点和叶子节点除外。 - 实际上上图没有画出叶子节点，在各类搜索树中，叶子节点通常是NULL，这样当搜索过程搜到了NULL，或者NULL指针，那就说明树里不包含要搜索的值，因为已经搜到叶子节点了还没搜到值。 - 4阶的树每个节点都至多只能有3个关键字，而且我们可以很容易的看出，每个节点的关键字数总是等于子节点-1。因此M阶树每个节点至多M-1个关键字。至少呢？至少M/2-1个呗(M/2向上取整)，总之就是比子节点数少1个。 - 节点中的关键字是有排列顺序的，一般按照升序排列，然后它们之间插入指向子节点的指针。举例，上图中QTX节点就是按照字母升序排列的，它们中间插入了指向子节点的指针。而且Q前面的指针指向的子节点，它的关键字一定全部小于Q，Q后面的指针指向的子节点，它的关键字一定大于Q且小于T。以此类推。
下面是我们搜索字母R的过程： 1. 字母R与根节点M比较，大于M，因此R一定在M的右子树里。 2. 字母R与M的右子节点QTX依序比较。可知Q<R<T。因此，R一定在Q和T之间的子树里。 3. 字母R与RS子节点依序比较，第一个关键字就是R，说明找到了要查找的关键字。
整个过程只用了3步，而索引的设计者会充分地利用硬盘存储的特性，使得你在使用索引的时候，从硬盘里恰好就是读取3次。每次读取一整块内容到内存里，而这一整块内容恰好就是一个节点包含的内容。 你肯定会问一个问题：为啥每个节点至多只有M-1个关键字，如果我插入新的关键字到一个已经满的节点里，会怎样？ 答案是：B树的这个节点需要进行裂变的过程，裂变成两个节点，然后多余出来的一个关键字，上升到父节点去。如果父节点也满了，就把父节点也分裂，再向上提关键字，如果根节点也满了，就会出现新的根节点，原根节点裂变，树的高度+1。详情请看那篇文章。
B树高度公式： {% asset_img gongshi.gif 公式 %} 其中m代表阶数，N代表关键字总数。m/2要向上取整。
另外，你应该可以知道，B树查询的时间复杂度是O(log2n)。由于我的markdown暂时没开公式功能，这个是以2为底……
B+树数据结构介绍： 和B树相比，B+树针对应用场景做了一些改变，或者可以说是优化…… B+树结构如下： {% asset_img b+tree.png B+Tree %} 然后我们可以看出它和B树相比有如下变化： - 它的叶子节点不再是NULL了，而是保存了完整数据的节点(也有可能只保存指向数据的指针)，比如上图中1到7完整的7个数据都保存在叶子节点中。 - 它的非叶子节点变成了纯粹的索引节点，保存着索引数据，而索引数据只起到索引的作用，最终获取数据是在叶子节点进行的。 - 叶子节点内部的关键字是按照升序排列的，而且叶子节点之间也通过指针连接在了一起。
这样有什么好处呢？ 可以看到，B+树利用叶子节点将数据给弄到了一起，使得B树拥有了链表的特性。这种特性对范围查询支持的比较好。 举个例子，如果你要查询树中大于3的全部数据，在一个普通的B树里，怎么做？ 如果在上面的B+树里，事情就简单的多，首先找到数据3，就和B树的查询过程是一样的，当你找到了数据3，那么接下来就是使用叶子节点们形成的链表，依次遍历叶子节点，就能取到3以后所有的数据了，这样的时间复杂度才是O(n)。
Mysql的两个主要引擎InnoDB和MyISAM都使用B+树来组织索引。 但是它们的结构略有不同。 ##### InnoDB引擎的索引结构： 对于主索引(即主键索引)，InnoDB的索引如下图： {% asset_img innodb1.png 聚簇索引 %} 这种索引结构被称为聚簇索引，它有以下特点： - 可以看到，InnoDB的主索引是B+树，注意，这个图画的有问题，每个节点的最左边应该也有指针 - 主索引的叶子节点正是数据表，数据既是索引，索引既是数据。 - 由于上一条特性，可以说InnoDB的每张表都至少有一个索引，正因如此，必须为表指定主键，如果你没有显式指定主键，引擎会从你的唯一非空索引中选择一个代替，如果选择不出来，就创建隐藏的列来作为主键。 - 可以知道，主键最好选择数字类型的列，而且最好是有自增规律的列。因为，如果主键是具有自增规律的列，B+树构造的过程就会减少很多次重新构建子树的过程从而减少开销。由于InnoDB在硬盘上的存储方式，还可能有效减少频繁分页产生的碎片。(使用随机UUID作为主键是这里的反例，如果害怕顺序的id有安全性问题，可在应用层对id进行加解密) - 一个表只能有一个聚簇索引，因为数据只能存放在一个地方。
对于辅助索引(除了主索引以外的其他索引)，InnoDB的索引如下图： {% asset_img innodb2.png 辅助索引 %} 这种索引结构有以下特点： - 也是一个B+树，注意，和上图一样，每个节点最左边应该也有指针 - 叶子节点不再是数据表，而是索引的列，当通过B+树找到了某一个记录后，引擎将得到一个主键值，然后使用主键值再到主索引里面找到真正的数据行。因此，辅助索引总是要进行两次B+树查找 - 之所以得到的是主键值而不是物理地址的指针，是为了解决数据插入时维护索引代价高的问题。如果辅助索引保存的是主键值，那么任何数据的插入和删除操作都不需要费力去维护辅助索引。 - 可以知道，为什么主键选择数字类型的列，而不是字符串，因为字符串类型的列占用更多的空间，主键越大，辅助索引们会跟着更大。