首页 > 代码库 > 索引基础知识
索引基础知识
一、索引的优缺点
索引的优点（为什么要有索引）
1、快速取数据
2、保证数据记录的唯一性
3、加快表的连接速度
4、在使用ORDER by、group by子句进行数据检索时，利用索引可以减少排序和分组的时间。
索引的缺点
1、索引需要占物理空间。
2、当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。
二、索引的本质
其实， 索引的本质是一个查找问题。索引一般都是用BTree或者BTree的变种（包括B+树、B-树、B*树）
B树（二叉树）
BTree即二叉搜索树。如下图所示。这个的查询应该不用说大家都知道。
如果这个BTree是平衡二叉树，那么他的查询性能是逼近二分查找的。但是如果是下图所示，那么查询的性能会非常差。如何将一棵树转换为平衡二叉树，这个留着以后写。
B-树
是一种多路搜索树（并不是二叉的）：
1、定义任意非叶子结点最多只有M个儿子；且M>2；
2、根结点的儿子数为[2, M]；
3、除根结点以外的非叶子结点的儿子数为[M/2,M]；
4、每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5、非叶子结点的关键字个数=指向儿子的指针个数-1；
6、非叶子结点的关键字：K[1],K[2], …, K[M-1]；且K[i] < K[i+1]；
7、非叶子结点的指针：P[1], P[2],…, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8、所有叶子结点位于同一层；
如：（M=3）的一个B-树如下：
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；
B-树有如下特性：
1、关键字集合分布在整颗树中；
2、任何一个关键字出现且只出现在一个结点中；
3、搜索有可能在非叶子结点结束；
B+树
B+树是B-树的变体，也是一种多路搜索树。其定义基本与B-树同，除了以下几点：
1、非叶子结点的子树指针与关键字个数相同；
2、非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树（B-树是开区间）；
3、为所有叶子结点增加一个链指针；
4、所有关键字都在叶子结点出现；
B+树有如下特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
总结如下：
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
该部分参考了http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
三、索引的分类
按照数据库中可以创建的索引类型来分：
普通索引
这是最基本的索引类型，而且它没有唯一性之类的限制。
创建普通索引的方法如下：CREATE INDEX<索引的名字> ON tablename(列的列表)
唯一索引
不允许其中任何两行具有相同索引值的索引
创建唯一索引的方法如下：CREATEUNIQUE INDEX <索引的名字> ON tablename(列的列表)
主键索引
其实主键索引是唯一索引的一种特殊类型。主键索引支持，在创建表的主键时，主键索引会自动创建。
聚集索引（也叫聚簇索引）
在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。
聚集索引一个表只能有一个，而非聚集索引一个表可以存在多个。
与非聚集索引相比，聚集索引通常提供更快的数据访问速度。
四、索引使用策略及优化
1、小的数据类型通常更好
越小的数据类型通常在磁盘、内存和CPU缓存中都需要更少的空间，处理起来更快。
2、简单的数据类型更好
整型数据比起字符，处理开销更小，因为字符串的比较更复杂。在MySQL中，应该用内置的日期和时间数据类型，而不是用字符串来存储时间；以及用整型数据类型存储IP地址。
3、尽量避免NULL
应该指定列为NOT NULL，除非你想存储NULL。在MySQL中，含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。你应该用0、一个特殊的值或者一个空串代替空值。
4、如果对多列进行索引(组合索引)，列的顺序非常重要
MySQL仅能对索引最左边的前缀进行有效的查找。例如：假设存在组合索引it1c1c2(c1,c2)，查询语句select * from t1 where c1=1 and c2=2能够使用该索引。查询语句select *from t1 where c1=1也能够使用该索引。但是，查询语句select * from t1 where c2=2不能够使用该索引，因为没有组合索引的引导列,即，要想使用c2列进行查找，必需出现c1等于某值。
索引基础知识