MySQL知识体系——索引

本文直切主题，针对InnoDB引擎描述索引及优化策略。在开始之前，需要读者了解：1）二叉查找树（包括2-3查找树、红黑树等数据结构）2）MySQL的InnoDB引擎基础知识

索引初探

要了解索引，当然要了解其数据结构。树有很多应用，流行的用法之一是包括UNIX和DOS在内的许多常用操作系统中的目录结构，二叉查找树又是Java中两种集合类TreeSet和TreeMap实现的基础。那么对于数据库，I/O是其性能瓶颈所在，减少树的深度是直接有效的，BTree和B+Tree应运而生。

BTree和B+Tree（Balance-Tree，多路搜索树，非二叉）

BTree

BTree是一种查找树，如同二叉查找树，红黑树等，都是为提高查找效率而产生的，BTree也是如此，可以把它看做二叉查找树的优化升级。二叉查找树的特点是每个非叶节点都最多只有两个子节点，但是当数据量非常大时，二叉查找树的深度过深，搜索算法自根节点向下搜索时，需要访问的节点也就变的相当多。如果这些节点存储在外存储器（磁盘）中，每访问一个节点，相当于就是进行了一次I/O操作，随着树高度的增加，频繁的I/O操作一定会降低查询的效率。BTree改二叉为多叉，每个节点存储更多的指针信息，以此达到减少树的深度、降低I/O操作数。

使用BTree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。

定义（对于一个m阶BTree）

•  根节点至少有两个子节点（除非根结点为叶节点）
•  每个节点有m-1个关键字，并且以升序排列
•  位于 m-1和m 关键字的子节点的值位于 m-1和m 关键字对应的值之间
•  其它节点至少有m/2个子节点

特性

•  关键字集合分布在整棵树中；
•  任何一个关键字出现且只出现在一个节点中；
•  搜索有可能在非叶节点结束；
•  其搜索性能等价于在关键字全集内做一次二分查找；
•  自动层次控制。

B+Tree

InnoDB 存储引擎在绝大多数情况下使用B+Tree建立索引，B+Tree也是关系型数据库中最为常用和有效的索引结构，但是B+Tree索引并不能找到一个给定键对应的具体值，它只能找到数据行对应的页，然后正如上一节所提到的，数据库把整个页读入到内存中，并在内存中查找具体的数据行。

定义（其定义基本与 BTree同，除了：）

•     所有叶节点之间都有一个链指针；
•     所有关键字都在叶子结点出现；
•     非叶子节点只存储键值信息，数据记录都存放在叶节点中。

特性

•  单节点可以存储更多的元素，使得查询磁盘IO次数更少，更加高效的单元素查找；
•  所有查询都要查找到叶子节点，查询性能稳定；
•  叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接，范围查找性能更优。

区别

      B+Tree是BTree的一种变形树，它与BTree的差异在于：

•  B+Tree只有达到叶子结点才命中（BTree可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
•  BTree树每个叶子节点都有双向指针；
•  BTree分支节点和叶节点均保存记录的关键码和记录的指针；B+Tree分支节点只保存记录关键码的复制，无记录指针。所有记录都集中在叶节点一层，并且叶节点可以构成一维线性表，便于连续访问和范围查询。 

聚集索引和辅助索引

数据库中的 B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index），它们之间的最大区别就是，聚集索引中存放着一条行记录的全部信息，而辅助索引中只包含索引列和一个用于查找对应行记录的“书签”。即在数据库的聚集索引中，叶子节点直接包含卫星数据。在辅助索引（NonClustered Index）中，叶节点带有指向卫星数据的指针。

聚集索引

InnoDB使用了聚集索引存储数据。

与非聚集索引的区别则是，聚集索引既存储了索引，也存储了行值。当一个表有一个聚集索引，它的数据是存储在索引的叶子页（leaf pages）上的。因此可以说InnoDB是基于索引的表。

当我们使用聚集索引对表中的数据进行检索时，可以直接获得聚集索引所对应的整条行记录数据所在的页，不需要进行第二次操作。

索引的建立规则

•  如果一个主键被定义了，那么这个主键就是作为聚集索引
•  如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引
•  如果没有主键也没有合适的唯一索引，那么InnoDB内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，改列的值会随着数据的插入自增

辅助索引

辅助索引，也叫做非聚集索引，叶节点不包含行的全部数据。除了包含关键字外，还包含了一个标记，这个标记用来告诉InnoDB引擎从哪里可以找到与索引相对应的行数据。由于InnoDB引擎是索引组织表，因此，这个标记就是相应的行数据的聚集索引关键字。

辅助索引的存在并不影响数据在聚集索引中的组织，因此一个表可以有多个辅助索引。

使用辅助索引查找一条表记录的过程：通过辅助索引查找到对应的关键字，最后在聚集索引中使用关键字获取对应的行记录，这也是通常情况下行记录的查找方式。

使用建议

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!