数据库是我们开发编程中不可缺少的模块，而数据库的索引又是重中之重。
在关系数据库中，索引是一种对数据库表中的值进行排序的存储结构。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。 索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值，然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快，可快速访问数据库表中的特定信息。
在关系型数据库中，主键，唯一键，普通键，都可以作为数据库的索引。
说到索引的数据结构，我们先来看下大家熟悉的二叉树。
如图是一个二叉查找树，在二叉查找树中，我们可以使用二分查找法，去检索需要的数据。 那为什么不用二叉树去作为索引的数据结构呢？如图所示的二叉树，如果我们删除了数据为6的节点，增加一个数据为10的节点，那此二叉树便成为了一个线形二叉树。也就是说，在插入删除的过程中，二叉树可能回演变成线性结构，线性结构会明显降低查询的效率；同时，二叉树在数据较多时，深度狠深，也不利于数据的查找。
我们再来看一下B树。 什么是B树呢，B树，又称B-树，它具有以下特点： （1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则； （2）它是一个多阶树，他的叶子节点和非叶子节点都记录有关键字； （3）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null。
B树的这些规则保证了关键字信息的顺序排列，并且在B树中进行删除增加操作时，b树仍然会保持树形结构。
显然B树相较于平衡二叉树，更加适合做索引的数据结构，但是呢，我们常用的mysql用的却并不是B树，而是更适合的B+树。
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，来看下B+树： B+树具有以下特点： （1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引； （2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样； （3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
所以，用B+树作为索引结构，有着以下优点： （1）B+树的中间节点不保存数据，是纯索引,但是B树的中间节点是保存数据和索引的,相对来说,B+树在磁盘页中能容纳更多节点元素。 （2）B+树每次查询都要从根节点一直查到叶节点，所以查询效率更加稳定。 （3）因为每个叶子节点都存放了指向下一个节点的指针，且关键数据有序排列，所以在范围查找中，B+树更占优势。 （4）增删节点时，效率更高，因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储。
我们常用的Mysql就是默认采用了B+树作为索引结构。
在我们创建索引时，可以看到mysql也是支持hash索引结构的，我们再来简单介绍下hash索引。 哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。 听起来很吊，但是hash索引虽然再等值查询时占有一定的优势，但是它相比于B+tree却有一些无法弥补的缺点： （1）它仅仅能满足等值查询，不支持范围查询。 （2）无法进行数据的排序操作。 （3）不支持多列联合索引的最左匹配规则。因为hash索引的联合索引，是把多个键值房子一起算hash值的。 （4）遇到大量hash值相等的情况后性能下降。
综上，mysql采用了默认B+tree作为索引结构，也支持hash结构作为索引的方式。
我们再来看下聚簇索引和非聚簇索引。
聚簇索引，也就是说，B+树的叶子节点保存的不仅仅是索引键的值，还保存了位于同一行记录里的其他列的信息，同时，由于聚簇索引决定了表存储数据时的物理排列顺序，所以一个表只有一个聚簇索引。 非聚簇索引文件只为索引码的某些值建立索引项，也就是说，叶子节点仅保存了键位信息和该行数据的地址或主键。
再来说下Mysql的两种存储引擎采用聚簇索引和非聚簇索引的区别。 对于innodb来说，每张表有且只有一个聚簇索引。（优先使用主键作为聚簇索引，没有主键则采用该表的唯一非空索引，如果都没有，innodb中会自动生成一个隐藏主键作为聚簇索引。） 同时，它的表数据和这个索引会存储在一起。而它的其他非聚簇索引的B+树的叶子节点中，则只存储了该行的主键值。所以，当使用非聚簇索引去查询的时候，数据库会先查到索引本身，再根据和索引存储再一起的主键，去聚簇索引中查询数据。如图所示：
对于myisam来说，它的表索引全是非聚簇索引，每张表可以有多个非聚簇索引，它的数据和索引也没有存在一起，它的B+树叶子节点中只存储了数据地址，查询时如图所示：
在我们平时的开发编程中，难免会和索引打交道。所以，只有更多的去了解索引，去了解索引的数据结构以及不同存储引擎中索引的区别等知识，才能让我们在解决平时遇到索引问题时游刃有余。
