数据库常见索引结构

雨点打透心脏的1/2处 2021-12-12 15:57 255阅读 0赞

# B树 #

即二叉搜索树：

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如：

![Center][]

B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

如：

![Center 1][]

但B树在经过多次插入与删除后，有可能导致不同的结构：

![Center 2][]

右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；

实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的策略。常见的平衡二叉树有：AVL，RBT，Treap，Splay Tree。

# 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）

![Center 3][]

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B-树的特性：

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.其搜索性能等价于在关键字全集内做一次二分查找；

5.自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

![Center 4][]

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；

由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

# B+树 #

B+树是B-树的变体，也是一种多路搜索树：

1.其定义基本与B-树同，除了：

2.非叶子结点的子树指针与关键字个数相同；

3.非叶子结点的子树指针P\[i\]，指向关键字值属于\[K\[i\], K\[i+1\])的子树（B-树是开区间）；

5.为所有叶子结点增加一个链指针；

6.所有关键字都在叶子结点出现；

如：（M=3）

![Center 5][]

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；

**小结**

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；

所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

# 位图索引 #

## 1.案例 ##

有张表名为table的表，由三列组成，分别是姓名、性别和婚姻状况，其中性别只有男和女两项，婚姻状况由已婚、未婚、离婚这三项，该表共有100w个记录。现在有这样的查询：     select \* from table where Gender=‘男’ and Marital=“未婚”;

<table style="width:699px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> 姓名(Name) </td> 
 <td style="vertical-align:top;"> 性别(Gender) </td> 
 <td style="vertical-align:top;"> 婚姻状况(Marital) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 张三 </td> 
 <td style="vertical-align:top;"> 男 </td> 
 <td style="vertical-align:top;"> 已婚 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 李四 </td> 
 <td style="vertical-align:top;"> 女 </td> 
 <td style="vertical-align:top;"> 已婚 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 王五 </td> 
 <td style="vertical-align:top;"> 男 </td> 
 <td style="vertical-align:top;"> 未婚 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 赵六 </td> 
 <td style="vertical-align:top;"> 女 </td> 
 <td style="vertical-align:top;"> 离婚 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 孙七 </td> 
 <td style="vertical-align:top;"> 女 </td> 
 <td style="vertical-align:top;"> 未婚 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> ... </td> 
 <td style="vertical-align:top;"> ... </td> 
 <td style="vertical-align:top;"> ... </td> 
 </tr> 
 </tbody> 
</table>

1）不使用索引

不使用索引时，数据库只能一行行扫描所有记录，然后判断该记录是否满足查询条件。

2）B树索引

对于性别，可取值的范围只有'男','女'，并且男和女可能各站该表的50%的数据，这时添加B树索引还是需要取出一半的数据， 因此完全没有必要。相反，如果某个字段的取值范围很广，几乎没有重复，比如身份证号，此时使用B树索引较为合适。事实上，当取出的行数据占用表中大部分的数据时，即使添加了B树索引，数据库如oracle、[**MySQL**][MySQL]也不会使用B树索引，很有可能还是一行行全部扫描。

## 2.位图索引出马 ##

如果用户查询的列的基数非常的小， 即只有的几个固定值，如性别、婚姻状况、行政区等等。要为这些基数值比较小的列建索引，就需要建立位图索引。

对于性别这个列，位图索引形成两个向量，男向量为10100...，向量的每一位表示该行是否是男，如果是则位1，否为0，同理，女向量位01011。

<table style="width:680px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> RowId </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 2 </td> 
 <td style="vertical-align:top;"> 3 </td> 
 <td style="vertical-align:top;"> 4 </td> 
 <td style="vertical-align:top;"> 5 </td> 
 <td style="vertical-align:top;"> ... </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 男 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 女 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> &nbsp;... </td> 
 </tr> 
 </tbody> 
</table>

对于婚姻状况这一列，位图索引生成三个向量，已婚为11000...，未婚为00100...，离婚为00010...。

<table style="width:680px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> RowId </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 2 </td> 
 <td style="vertical-align:top;"> 3 </td> 
 <td style="vertical-align:top;"> 4 </td> 
 <td style="vertical-align:top;"> 5 </td> 
 <td style="vertical-align:top;"> ... </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 已婚 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 未婚 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 离婚 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

当我们使用查询语句“select \* from table where Gender=‘男’ andMarital=“未婚”;”的时候 首先取出男向量10100...，然后取出未婚向量00100...，将两个向量做and操作，这时生成新向量00100...，可以发现第三位为1，表示该表的第三行数据就是我们需要查询的结果。

<table style="width:680px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> RowId </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 2 </td> 
 <td style="vertical-align:top;"> 3 </td> 
 <td style="vertical-align:top;"> 4 </td> 
 <td style="vertical-align:top;"> 5 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 男 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> and </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 未婚 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 结果 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 <td style="vertical-align:top;"> 0 </td> 
 </tr> 
 </tbody> 
</table>

## 3.位图索引适应场景 ##

上面讲了，位图索引适合只有几个固定值的列，如性别、婚姻状况、行政区等等，而身份证号这种类型不适合用位图索引。

此外，位图索引适合静态数据，而不适合索引频繁更新的列。举个例子，有这样一个字段busy，记录各个机器的繁忙与否，当机器忙碌时，busy为1，当机器不忙碌时，busy为0。

这个时候有人会说使用位图索引，因为busy只有两个值。好，我们使用位图索引索引busy字段！假设用户A使用update更新某个机器的busy值，比如update table set table.busy=1 where rowid=100;，但还没有commit，而用户B也使用update更新另一个机器的busy值，update table set table.busy=1 where rowid=12; 这个时候用户B怎么也更新不了，需要等待用户A commit。

原因：用户A更新了某个机器的busy值为1，会导致所有busy为1的机器的位图向量发生改变，因此数据库会将busy＝1的所有行锁定，只有commit之后才解锁。

# Hash索引 #

索引列会被存储在匹配到的hash bucket里面的表里，这个表里会有实际的数据行指针，再根据实际的数据行指针查找对应的数据行。

![Center 6][]

概括来说，要查找一行数据或者处理一个where子句，SQL Server引擎需要做下面几件事

1、根据where条件里面的参数生成合适的哈希函数

2、索引列进行匹配，匹配到对应hash bucket，找到对应hash bucket意味着也找到了对应的数据行指针（row pointer）

3、读取数据

哈希索引比起B树索引简单，因为它不需要遍历B树，所以访问速度会更快

![Center 7][]

Hash索引的缺点：

1、因为Hash索引比较的是经过Hash计算的值，所以只能进行等式比较，不能用于范围查询

2、由于哈希值是按照顺序排列的，但是哈希值映射的真正数据在哈希表中就不一定按照顺序排列，所以无法利用Hash索引来加速任何排序操作

3、不能用部分索引键来搜索，因为组合索引在计算哈希值的时候是一起计算的。

4、当哈希值大量重复且数据量非常大时，其检索效率并没有Btree索引高的。

[Center]: /images/20211210/36f380437fcf4da995dd0b8716f19c46.png
[Center 1]: /images/20211210/dcb219e6775041f19915d9af5d0c3afa.png
[Center 2]: /images/20211210/05863219619e4d9688b09949a608ab0a.png
[Center 3]: /images/20211210/c275cefcf21f4c2da378a7cc04234f81.png
[Center 4]: /images/20211210/d313977bdd8645dea97d3227a2af1159.png
[Center 5]: /images/20211210/c8b5d3bf573846b3a406e56ae819a85c.png
[MySQL]: http://lib.csdn.net/base/14
[Center 6]: /images/20211210/59e04481bc324ff681edc24b8cbb61af.png
[Center 7]: /images/20211210/4317ed98519a43edb5d0b71026655541.png