数据结构索引之杀死攻略（三）

àì夳堔傛蜴生んèń 2022-05-15 03:50 209阅读 0赞

接上一篇《数据结构索引之杀死攻略（二）》：[https://blog.csdn.net/wydyd110/article/details/81945803][https_blog.csdn.net_wydyd110_article_details_81945803]

**目录**

4 位索引技术（位图索引BitMap Index）

4.1 位图索引的故事

4.2 位图索引是啥？？？

4.3 位图索引的适用条件

5 红黑树

5.1 红黑树的特征

5.2 红黑树的阶

5.3 红黑树的插入

5.4 红黑树的删除

5.5 红黑树的总结及应用

--------------------

# 4 位索引技术（位图索引BitMap Index） #

## 4.1 位图索引的故事 ##

摘抄自Tomas这位Oracle大佬编著的《Expert Oracle Database Architecture-9i and 10g programming Techniques and Solutions》

![70][]

一日，一群Java开发者找到Tom先生，说他们新开发的系统已经上线，但性能及其低下，他们问Tom先生能不能替他们看看问题到底出在什么地方。他们告诉Tom，他们的系统采用JSP+EJB+Oracle的典型三层架构，其中EJB中的SQL是由第三方工具产生的。Tom同志一听到EJB，就知道这个系统是不能采用SQL代码跟踪的方法来进行性能调优了。于是，Tom同志告诉这些心急火燎的Java开发者，你们系统的问题肯定在浏览器到数据库之间，但具体问题出在什么地方，我需要看看你们的数据库。

于是，Tom同志远程连接到他们的测试数据库（注意不是生产数据库），查看了几个动态性能视图(V$LOCK和V$SQL)，最后终于发现了问题的所在。Tom同志发现他们的数据库中有一个位图索引(Bitmap Index)最为可疑，这个索引是建立在一个PROCESS\_FLAG的字段上。PROCESS\_FLAG字段表示该记录是否被处理了，可能值只有两个，一个是未处理(N)，一个是已经处理(Y)。当记录初次插入数据库时，该字段的值为N，但其它进程读取并处理那些未处理的记录(值为N的记录)后，这个字段的值就更新为Y。

Tom就问这些Java开发者，你们为什么要在这个PROCESS\_FLAG字段上建立位图索引呢？

其中有一个开发者振振有词的说，这是为了提高查找速度，一旦建立了位图索引，我们的程序就能快速找到那些数值为N的记录，然后处理。随后，他又拿出一本大部头的Oracle数据库参考手册，对Tom同志说，这书上都是这么说的，**对那些数值非常少的字段**，比如，我们的PROCESS\_FLAG字段只有两个值，**就应该建立位图索引**，这难道有什么问题吗？

Tom同志微微一笑，没有直接回答。只见他打开SQL Plus，连接到他的本地Oracle实例，给这群开发者演示了下面及其简单的SQL代码。

SQL> create table t(processed\_flag varchar2(1));

Table created.

SQL> create bitmap index t\_idx on t(processed\_flag);

Index created.

SQL> insert into t values('N');

1 row created.

刚才那位振振有词的开发者不服气的说，这有什么，不是很正常吗？接着Tom又打开了一个SQL Plus窗口，并连接到本地数据库，键入下面的SQL语句，奇怪的是这条SQL并不执行，而是一直在等待。下面是这条SQL的一个截图：

![70 1][]

这些Java开发者看到这里，惊讶得目瞪口呆。其中一个开发者犹豫地说，好像这个**位图索引只允许一个用户操作**，如果其它用户想同时操作这个索引，那他必须等第一个用户的请求处理完成，并且提交之后，才能进行，如果第一个用户不提交，那么他必须一直等待。Tom点头表示赞同，然后给他们作了一番详细的解释：

> Oracle数据库的位图索引(Bitmap Index)确实是针对那些数值稀疏(low-cardinality，低基数)的字段，但是还应记住的一点是，它是**针对那些值不经常改变的字段**。在实际应用中，如果某个字段的值需要频繁更新，那么就不适合在它上面创建位图索引。在位图索引中，如果你更新或插入其中一条数值为N的记录，那么相应表中数值为N的记录（可能成百上千条）全部被Oracle锁定，这就意味着其它用户不能同时更新这些数值为N的记录，其它用户必须要等第一个用户提交后，才能获得锁，更新或插入数据。

问题找到了，修正就很简单了，Tom建议这些开发者去掉了这个位图索引，然后在PROCESS\_FLAG字段上建立一个函数索引，只为那些数值为N的记录建立简单的B树索引就可以了。

故事讲完了，相信大家对位图索引还是一脸懵逼，稍安勿躁！！！

![70 2][]

## 4.2 位图索引是啥？？？ ##

![70 3][]

位图索引，顾名思义，与“位”有关。计算机中所有的数据最终都转换成二进制的形式进行存储或计算。每个二进制位的取值为0或1，而取值的确切含义是由具体的上下文环境决定的。在位图索引中，每一个二进制位代表了某一行中索引列的取值情况。

![70 4][]

有张表名为cat的表，现在要执行这样的查询：select \* from cat where gender=‘公’ and character=‘乖’;

![70 5][]

为性别字段构建位图索引，是则为1，不是则为0

![70 6][]

形成两个向量：公10110 母01001

--------------------

为性格字段构建位图索引，是则为1，不是则为0

![70 7][]

形成两个向量：凶11010 母00101

--------------------

当我们使用查询语句“select \* from cat where gender=‘公’ and character='乖';”的时候 首先取出公向量10110，然后取出乖向量00101，将两个向量做and操作，这时生成新向量00100，可以发现第三位为1，则奥利奥就是我们所要找的。

![70 8][]

## 4.3 位图索引的适用条件 ##

**（1）**位图索引适用于数值非常少的字段。如：性别，婚姻状况等，而身份证号这种类型不适合用位图索引。

**（2）**位图索引适用于数值不经常改变的字段。（不理解的盆友去细细品味文章开头的那个故事）

**（3）**位图索引只允许一个用户操作，不适用于并发环境，否则会导致死锁。（不理解的盆友去细细品味文章开头的那个故事）

终于干掉了位图索引，露出姨母般的微笑

![70 9][]

然而革命尚未结束，下面还有.................................................红黑树

![70 10][]

# 5 红黑树 #

推荐博文：[https://blog.csdn.net/wydyd110/article/details/81983918][https_blog.csdn.net_wydyd110_article_details_81983918]

## 5.1 红黑树的特征 ##

![70 11][]

## ![70 12][] ##

（5）红黑树是满二叉树，空叶结点也看作结点

（6）n 个内部结点的红黑树，树高最大是 2 log2 (n+1)+1

（7）阶为 k 的红黑树树高 最小是 k+1，最高是 2k+1

（8）左 < 中 < 右

## 5.2 红黑树的阶 ##

![70 13][]

## 5.3 红黑树的插入 ##

参考：[https://blog.csdn.net/wydyd110/article/details/80097246][https_blog.csdn.net_wydyd110_article_details_80097246]

## 5.4 红黑树的删除 ##

参考：[https://blog.csdn.net/wydyd110/article/details/80097250][https_blog.csdn.net_wydyd110_article_details_80097250]

## 5.5 红黑树的总结及应用 ##

![70 14][]

![70 15][]

AVL树和红黑树适合在内存中的作业，如map,set之类多为RB-tree实现。

B系列树适合外部存储应用，如在硬盘中的作业。

AVL：高度平衡的二叉树，一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。AVL树适合用于插入删除次数比较少，但查找多的情况。

红黑树：平衡二叉树，通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。

AVL树和红黑树都用旋转保持平衡

AVL树对每个插入操作最多需要两次次旋转（单/双旋），对每个删除操作最多需要O（logn）次旋转；

红黑树对每个插入和删除操作，任何不平衡都会在三次旋转之内解决。

[https_blog.csdn.net_wydyd110_article_details_81945803]: https://blog.csdn.net/wydyd110/article/details/81945803
[70]: /images/20220515/0a69226566804a7b9289f1ec7cd19468.png
[70 1]: /images/20220515/ac5e5388371a42b7a493634cb5b72780.png
[70 2]: /images/20220515/ee55e81b75db4925810ce7cc50638a20.png
[70 3]: /images/20220515/05e8fd62ea8949b3bbaaa71f2d4c03fe.png
[70 4]: /images/20220515/7d7719be81d8489a91d0206c2d68203f.png
[70 5]: /images/20220515/37fd45d9f79042b9b32cda5a67db3830.png
[70 6]: /images/20220515/151d1d13e5b84362b2f812ee81b94340.png
[70 7]: /images/20220515/2e0d85799edc4034a9a344ee245a26da.png
[70 8]: /images/20220515/c0dd729709164896a01014271d9fb5ee.png
[70 9]: /images/20220515/99cfb135262942349e6eff7f453a0443.png
[70 10]: /images/20220515/9977859db9064872bce1fa5e341793e4.png
[https_blog.csdn.net_wydyd110_article_details_81983918]: https://blog.csdn.net/wydyd110/article/details/81983918
[70 11]: /images/20220515/d9dfa98fc6ed468bbef2198dc43eb1e4.png
[70 12]: /images/20220515/484179f22d3147dd8cad7cc01fb6f04e.png
[70 13]: /images/20220515/c3e4cc12b12f4c56ba7eea51a89492f9.png
[https_blog.csdn.net_wydyd110_article_details_80097246]: https://blog.csdn.net/wydyd110/article/details/80097246
[https_blog.csdn.net_wydyd110_article_details_80097250]: https://blog.csdn.net/wydyd110/article/details/80097250
[70 14]: /images/20220515/7449c1cc4b8f488a80e0c22ee86feb0c.png
[70 15]: /images/20220515/4db518803b7e4bf78038f532c96c7637.png