索引的类型与详解

首先强调一点，很多人认为索引是DBA那种角色做系统优化的时候才用得到，跟程序员没关系，所以不需要很深刻的掌握，只需要操作数据库时候会用就好。这个观点是大错特错的！

索引是一种数据结构，不只是应用于数据库，而数据结构是程序开发人员必须掌握的一门技能，数据结构的学习将会充满整个职业生涯。

 

B树索引：

还是得先要搞清楚一个概念，B-balance，所以B树索引就是个多叉平衡树。它有3个版本：B-tree，B+tree和B*tree，其中B-tree就是B树，是B树的原型版本，网上很多资料把B树和B-Tree当成两种结构是错误的。

B-Tree：

        1每层、每个节点内的关键字都是排好序的

2叶子节点都在同一层，维护了结果的指针

3非叶子结点有上下两部分，上部分是关键字，下部分是儿子节点的指针，上比下少1，上部分内也有关键字所指的指针

4一次寻址从根节点开始，在上部分直接命中的话寻址结束，根据指针跳转到内容；上部分没有命中根据大小关系确定通过哪个叶子节点继续往下找直到命中。

5索引的插入和删除都要维持B树的平衡，规则是非叶子节点要有【M/2，M】个儿子，每个节点存放【M/2,M】个指针，平衡被破坏后进行分裂或合并。

3阶B树图：

        

 

B+Tree：

        B+是B基础上的变种，主要做了3点修改：

        1每个节点内上下两部分是相等的，上部分还是关键字，下部分还是子指针，但是P与关键字的关系从B数的开区间变成了[ k[i],k[i+1])半闭区间

        2中间节点不再保存内容指针，也就是所就算在中间节点被命中也无法直接退出索引，需要一直走到叶子节点才能获取指针信息。这种设计减少中间节点占用空间，使内存一次加载更多的中间信息。时间复杂度上从B树的不稳定变成了稳定，因为中间不会退出，索引有多深就要检索多少次。

        3叶子节点按关键字的大小从小到大顺序连接，所以B+树提供了从根节点和从最小叶子节点两种检索方式。

 

3阶B+树图：

        

 

B*Tree：

B*Tree是在B+Tree基础上的变种，有2点变化：

1中间节点增加了指向兄弟节点的索引

2中间节点存放的最低关键字个数从M/2改成2M/3

 

3阶B*Tree：

     

 

3种B数平行对比下：

B中间可退出，B+一定要执行到底。

B+分裂时自己分离1/2形成新节点添加到父节点完事，B*分裂先尝试借助兄弟节点空余空间的帮忙，如果兄弟也满了才跟兄弟各凑1/3形成新节点，所以B*比B+分配新节点概率小。

 

位图索引：

我自己觉得另一个名字更好理解它，我把它叫“打点索引”，小学生分1-6个年级，人类分男女，成年人分各种职业，出生地分各个省份，这些可以在穷举的稳定的状态位上就可以建成位图索引。每个状态位维护一行记录，从左到右对属于这个状态位的内容进行大点，例如男女我可以打出两行断断续续的点。

基于位图索引的单条件查询，只要去找到大点的记录的指针；基于位图的联合查询，就是状态位间的与或运算。

但是位图索引在我自己的项目中是被命令禁止的！因为位图索引存在一个先天的缺陷：竞争。

例如我们项目中需要管理很多设备资源，例如交换机，而这些资源的端口分为占用和空闲两个状态，我们曾经给这个状态位添加了位图索引，结果系统崩溃了。因为端口状态的变更，也就是表记录这个状态的update会引起锁等待。虽然端口的update只update自己，属于行锁，所以多个端口的同时update理论上不会有问题，但是数据库在维护位图索引的时候所有端口的状态是维护到同一列中的，这就变相的成为了表锁。

 

倒排索引：

倒排索引本质上就是B树索引，假如我们给每个人身份证号建一个B树索引，我要查身份证号是37开头的这个索引运转的就很完美。如果我的业务要求查“最后一位是X的身份证号”，我这个索引就毫无意义了。所以为了迎合这种需求，我把每个人身份证号倒过来再建一次B树，这就是倒排索引，倒排索引是根据业务来决定如何创建的。

 

散列索引：

像HashTable，对关键字进行Hash后维护HashCode和内容指针，散列索引进行等于查询是速率很快，但是无法进行范围查询。