这几天通过阅读sql索引的概述和索引的原理对这两篇文章做一个总结。

首先来简述一下什么是索引，索引相当于书的目录，它可以对特定值快速查找与定位。

索引在SQL优化中占了很大的比重，索引用的好，查询效率会有很大的提升，但索引并不只会提升查询效率，相反索引运用不当也会降低查询效率。

在一般情况下，数据量少的情况下，有无索引查询的效率几乎相差无几；数据量大的情况下，要查询表中的少量数据，有索引的查询就会优于没有索引的查询。

我们按照功能逻辑来分的话，索引有4类：普通索引、索引、主键索引、全文索引

普通索引：基础的索引，无约束，只为提高查询效率

索引：在普通索引中加 的约束，索引在表中可以有多个

主键索引：在索引上加个不为空的约束，主键索引在表中只有一个

全文索引：建立索引，再对索引进行搜索的过程

按照物理实现方式来分，索引有两类：聚集索引（二级索引）、非聚集索引（辅助索引）

聚集索引：按照主键来排序存储数据

非聚集索引：先找索引再根据索引取出数据

注意：聚集索引叶子节点存数据，非聚集索引叶子节点存数据位置；聚集索引只能有一个，非聚集索引有多个；聚集索引只在查询用时效率高，在进行插入、删除、更新等操作效率比非聚集索引低。

按字段个数来分，有两种：单一索引、联合索引

单一索引：索引列为一列

联合索引：索引列为多列（顺序不同效率可能会有差别，按左匹配原则，从左的字段开始匹配）

因此在使用索引进行数据查询时，我们应该根据实际情况选择合适的索引帮助我们提升查询效率，避免错误运用索引导致查询效率降低。上面介绍了不同类别的索引，那么我们也可以使用合理的数据结构来使索引查找数据更加方便。

数据库有两种存储介质，分为内存和硬盘。内存容量有限，做临时存储，容易造成数据丢失；硬盘作为存储介质，我们在硬盘上用索引进行数据查找时，如果数据结构越易于索引查找，消耗时间也就越少。因此选取那种类型的数据结构就变得非常重要。

下面将介绍一些数据结构：

二分搜索树（Binary Search Treee）:

其特点是父节点的值大于左孩子的值小于右孩子的值。

因此在进行数据查找时，如果搜索的值等于根节点，返回根节点的值；如果搜索的值大于根节点的值，则在右子树上查找，反之在左子树上查找。一般在数据量小的情况下，二分搜索树深度小，数据检索的销量也会变高；但是当数据量变得庞大，二分搜索树深度就好变得很大，会造成数据检索的效率变低；还有一种特殊的情况，数据量不大，但二分搜索树在形式上退化成一条链，深度就好变得很大，影响数据检索的效率。

平衡二叉搜索树（ALV树）：

其继承了二分搜索树树的全部特点，但是它每个节点的左子树和右子树的高度差至多等于1.它很好的避免了二分搜索树的特殊情况，但当数据量变得庞大，其深度还是会变得很大，数据检索的效率依旧会降低。

红黑树（Red Black Tree）:

其特点为根节点为黑，所有叶子都是黑，节点为红或黑，每个红色节点的两个子节点都是黑色，从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。红黑树在进行数据检索相当于二分搜索树。

数堆（Treap）：

它是二分搜索树和堆合并构成的数据结构，其每个节点包括两个值，key值满足二分搜索树，weight值满足堆的性质。因此数堆利用weight值作为随机因子来调整二叉树的形状，使建立的二叉树较平衡，但面对庞大的数据量，数据检索效率还是会变低。

伸展树（Splay Tree）:

伸展树在面对数据查找时，为了缩短查找时间，在每次查找之后就会对树进行重构，把被查找的数据搬到离根附近的位置，但有时候也会和二分搜索树一样变成一条链，深度变大，数据检索效率变低。

B树（Balance Tree）：

M阶B数的特点：根节点的儿子数的范围为[2,M]，每个节点有k-1个关键字，k个孩子，孩子数量=关键字数量+1（k的范围是[ceil(M/2),M]），叶节点包含k-1个关键字（k的范围是[ceil(M/2),M]），所有叶子节点位于同一层。

M越大意味着存储的数据越多，深度降低，数据检索的效率比平衡二叉树高。

B+树：

有k个孩子就有k个关键字，非叶子节点的关键字同时存在子节点中，并且是在子节点中所有关键字的大。非叶子节点仅用于索引，只有叶子节点保存信息，所有关键字都在叶节点出现，叶节点构成一个有序链表，叶节点按照关键字的大小从小到大连接。

B+树查询效率更稳定。因为其只有叶子节点存储数据，查询效率更高，较B树来说深度更低，并且叶子节点是有序链表进行了链接，查询更方便。

因此MySQL中采用B+树作为数据结构，因为其效率更高，更适合进行关键字的范围查询。