Oracle课程设计B树

1、学 号： 课 程 设 计题 目B*树索引学 院计算机科学与信息工程学院专 业金融信息化服务外包班 级学生姓名指导教师2015年12月27日重庆工商大学课程设计成绩评定表学院：计信学院 班级： 学生姓名： 学号：项目分值优秀(100>x90)良好(90>x80)中等(80>x70)及格(70>x60)不及格(x<60)评分参考标准参考标准参考标准参考标准参考标准学习态度15学习态度认真，科学作风严谨，严格保证设计时间并按任务书中规定的进度开展各项工作学习态度比较认真，科学作风良好，能按期圆满完成任务书规定的任务学习态度尚好，遵守组织纪律，基本保证设计时间，按期完成各

2、项工作学习态度尚可，能遵守组织纪律，能按期完成任务学习马虎，纪律涣散，工作作风不严谨,不能保证设计时间和进度技术水平与实际能力25设计合理、理论分析与计算正确，实验数据准确，有很强的实际动手能力、经济分析能力和计算机应用能力，文献查阅能力强、引用合理、调查调研非常合理、可信设计合理、理论分析与计算正确，实验数据比较准确，有较强的实际动手能力、经济分析能力和计算机应用能力，文献引用、调查调研比较合理、可信设计合理，理论分析与计算基本正确，实验数据比较准确，有一定的实际动手能力，主要文献引用、调查调研比较可信设计基本合理，理论分析与计算无大错，实验数据无大错设计不合理，理论分析与计算有原则错误，实

3、验数据不可靠，实际动手能力差，文献引用、调查调研有较大的问题创新10有重大改进或独特见解，有一定实用价值有较大改进或新颖的见解，实用性尚可有一定改进或新的见解有一定见解观念陈旧论文(计算书、图纸)撰写质量50结构严谨，逻辑性强，层次清晰，语言准确，文字流畅，完全符合规范化要求，书写工整或用计算机打印成文；图纸非常工整、清晰结构合理，符合逻辑，文章层次分明，语言准确，文字流畅，符合规范化要求，书写工整或用计算机打印成文；图纸工整、清晰结构合理，层次较为分明，文理通顺，基本达到规范化要求，书写比较工整；图纸比较工整、清晰结构基本合理，逻辑基本清楚，文字尚通顺，勉强达到规范化要求；图纸比较工整内容空

4、泛，结构混乱，文字表达不清，错别字较多，达不到规范化要求；图纸不工整或不清晰指导教师评定成绩：指导教师签名： 年 月 日第 17 页 共 17 页课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题 目: B*树索引已知技术参数和设计要求：a) 时间要求为14周18周。b) 开发工具不限（oracle/sqlplus）。c) 开发平台不限（Linux）。d) 集成开发环境不限。e) 所用数据库不限（Oracle 10g）。f) 说明文档要求符合学校课程设计文档规范。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）B*树索引。(1) 什么是B*树(2

5、) B*索引的组织结构(3) 索引键压缩(作用及结构)(4) 反向键索引(作用及结构)(5) 降序索引(作用及结构)时间安排：1、研究分析什么是B*树，和同学讨论联系实际，历时2天。2、研究分析B*索引的组织结构，历时2天。3、研究分析索引键压缩，反向键索引，降序索引，历时4天。4、编写相关文档，历时2天。5、Oracle大型数据库课程设计文档的最后检查与修订，历时1天指导教师签名： 年 月 日目录1.什么是B*树52.B*索引的组织结构63.索引键压缩(作用及结构)74.反向键索引(作用及结构)8（1）.反向索引应用场合9（2）.使用反向索引的优点.9（3）.使用反向索引的缺点.9（4）.通

6、过一个实验简单演示一下反向索引的创建及修改145.降序索引（作用及结构）146.总结157.参考资料151.什么是B*树B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部 分数据移到兄弟结点中，再在原结点插入关

7、键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）。如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针，所以，B*树分配新结点的概率比B+树要低，空间使用率更高。 B*树索引就是我们说的“传统”索引，这是数据库中最常用的一类索引结构。其实现与二叉查找树类似，目标是减少oracle查找数据的时间。如果在一个数字列上有一个索引，那么理论上结构应该是这样的（图1）：图1 具体B*结构示意图  这个树最底层是叶子节点，包含索引键以及一个rowid（指向索引行）。叶子节点上面的称为分支块，用于在结构中实

8、现导航。例如：想在索引中找到值42，从树顶开始查找进入左分支，查找这个块，发现需要找的数据在“42.50”的叶子节点中。另外，叶子节点之间是双向链表结构。也就是查找区间数据很容易，比如这样的条件：where x between 20 and 300。oracle只要刚开始找到大于或等于20的记录所在的叶子节点，接着往下扫描，找到大于或者等于300的块。这期间可能会跨叶子节点扫描，由于叶子节点之间是双向链表，故很容易实现跨叶子节点扫描。  B*树有一个特点：所有的叶子节点都在同一层，也就是无论你查找哪一条数据，需要执行的I/O数据是一样的。一般的B*树都是2或者3层。无论这个表有多少行

9、数据，这样查找一条数据只需要2,3个I/O操作。2.B*索引的组织结构 一般的B*树结构如图 2所示。图 2 B*结构示意图最底层的数据块被称为叶子结点，叶子结点中包含了索引键值和其所对应的 ROWID 。其它的数据块被称为分支块,可用于定位相应的叶子结点。同时叶子结点之间也存在一个双 向链表，当对某个索引进行范围扫描时,可通过叶子结点之间的双向链表来进行检索而不用通过分支结点。每个索引最少有一个叶子结点，一个叶子结点中可包含多行索引数据。B*树索引中所有的叶子结点都应在同一层中,此层的高度也即称为这个索引的高度，因此可以说索引是高度平衡的。B*树索引最大的层次为24层，一个索引中最

10、多只能包含32个字段列。每个键的长度根据不同版本的数据块大小的不同而不同。分支块结点存储的是指向其下层结点的指针，每一个索引都有一个根结点，根结点所在的数据块在索引段中紧随段头信息所在的数据块。整个索引的层次被称为索引的高度 ，可通过数据库中视图 index_ stat 中的字段 height 查出，分支结点的层次被称为 blevel，可在数据字典 dba_indexes 中的字段 blevel 查出，需对索引进行分析才可计算出索引的高度和blevel 的值，即analyze index index _ name validate structure。索引的高度是由索引的分支结点的个数决定的，

11、而索引分支结点的个数又是由索引键值的长度和索引叶子结点的个数决定的。Oracle 数据库中的最小逻辑单元是数据库数据块，其大小由数据库初始化参数 DB_BLOCK_SIZE 所决定。所有的索引数据和表数据都是以数据块为单位存放的，同时每个索引数据块会存放相应的头信息。3.索引键压缩(作用及结构)信息检索系统中的两个主要数据结构:词典及倒排索引。下面将介绍对这两个数据结构的各种压缩技术,这些技术对于构建高效的 IR 系统非常关键。进行压缩的一个优点显而易见:它能够节省磁盘空间。要达到 14 的压缩比是非常容易的,也就是说可以降低 75%的索引存储开销。索引压缩还有两个隐含的优点。第一是能增加高速

12、缓存(caching)技术的利用率。在搜索系统中,词典中某些条目及其索引往往比其他条目及其索引的使用更频繁。例如：如果将一个频繁使用的查询词项t的倒排记录表放到高速缓存中,那么对仅由t构成的查询进行应答所需要的计算完全可以在内存中完成。如果采用压缩技术,那么高速缓存中就可以放更多的信息。当查询词项t的信息放在高速缓存时,处理查询t便不再需要进行磁盘操作,而只需将其倒排记录表在内存中解压缩即可。因此,我们能充分减少IR系统的应答时间。由于内存比磁盘更贵,所以,相对于磁盘空间的减少,采用高速缓存技术带来的速度提升是采用压缩技术的更主要的原因。 第二个隐含的优点是,压缩能够加快数据从磁盘到

13、内存的传输速度。高效的解压缩算法在现代硬件上运行相当快,这样将压缩的数据块传输到内存并解压所需要的总时间往往会比将未压缩的数据块传输到内存要快。举例来说,即使会增加在内存进行解压缩的开销,我们也可以 通过加载一个小很多的压缩倒排记录表来减少 I/O 时间。因此,在大部分情况下,使用压缩倒排记录表的检索系统会比没用压缩的系统的运行速度要快。 如果压缩的主要目的是为了节省磁盘空间,那么压缩算法的速度就不用特别考虑。但是, 如果要提高高速缓存利用率和磁盘到内存的传输率,则解压缩的速度必须要快。 【将词典看成单一字符串的压缩方法】采用定长方法来存储词项存在着明显的空间浪费。一种解决

14、上述缺陷的方法是,将所有的词项存成一个长字符串，并给每个词项增加一个定位指针,它在指向下一词项的指针同时也标识着 当前词项的结束。（就是目前构架中的var_data）实际上,按照词典顺序排序的连续词项之间往往具有公共前缀。因此,可以采用一种称为前端编码(front coding)的技术。 公共前缀被识别出来之后,后续的词项中便可以使用一个特殊的字符来表示这段前缀。假如一个表中，需要三列才能确认一行。那么我们在这个表示建立索引需要建立在这三列上。那么索引块的结构有可能是这样的：                

15、0; 图3索引块的结构   我们会发现，第一列和第二列有很多值是重复的。其实这个时候可以进行压缩，对于重复的值，只保存一份。比如：Sql代码 ： （1）<span style="font-size: x-small;">drop index t_idx;  （2）create index t_idx on  （3）t(owner,object_type,object_name)  （4）compress&

16、#160;&2;</span>    compress&2表示压缩两列，这样能节省空间，但是会增加寻找的难度。也就是说，如果现在已经占用了大量的cpu时间，那么创建索引以压缩 的方式，会使情况更糟糕。如果目前只是I/O操作比较多，那么压缩索引能加快处理速度，因为压缩之后的索引空间更少，那么块缓冲区应该能存放更多的索引块，块的命中率会提高。4.反向键索引(作用及结构)我们知道Oracle会自动为表的主键列建立索引，这个默认的索引是普通的B-Tree索引。对于主键值是按顺序(递增或递减)加入的情况，默认的B-Tree索引并不理想。

17、这是因为如果索引列的值具有严格顺序时，随着数据行的插入，索引树的层级增长很快。搜索索引发生的I/O读写次数和索引树的层级数成正比，也就是说，一棵具有5个层级的B -Tree索引，在最终读取到索引数据时最多可能发生多达5次I/O操作。因而，减少索引的层级数是索引性能调整的一个重要方法。如果索引列的数据以严格的有序的方式插入，那么B-Tree索引树将变成一棵不对称的"歪树"，如图 4所示：图4不对称的“歪树“而如果索引列的数据以随机值的方式插入，我们将得到一棵趋向对称的索引树，如图 5所示：图5对称的索引树比较图4和图5，在图4中搜索到A块需要进行5次I/O操作，而图 5仅需要

18、3次I/O操作。 既然索引列数据从序列中获取，其有序性无法规避，但在建立索引时，Oracle允许对索引列的值进行反向，即预先对列值进行比特位的反向，如 1000,10001,10011,10111,1100经过反向后的值将是0001,1001,1101,0011。显然经过位反向处理的有序数据变得比较随机了，这样所得到的索引树就比较对称，从而提高表的查询性能。 但反向键索引也有它局限性：如果在WHERE语句中，需要对索引列的值进行范围性的搜索，如BETWEEN、<、>等，其反向键索引无法使用，此时，Oracle将执行全表扫描；只有对反向键索引列进行 <>和 = 的比较操作

19、时，其反向键索引才会得到使用。（1）.反向索引应用场合1）发现索引叶块成为热点块时使用 通常，使用数据时（常见于批量插入操作）都比较集中在一个连续的数据范围内，那么在使用正常的索引时就很容易发生索引叶子块过热的现象，严重时将会导致系统性能下降。2）在RAC环境中使用 当RAC环境中几个节点访问数据的特点是集中和密集，索引热点块发生的几率就会很高。如果系统对范围检索要求不是很高的情况下可以考虑使用反向索引技术来提高系统的性能。因此该技术多见于RAC环境，它可以显著的降低索引块的争用。（2）.使用反向索引的优点 最大的优点莫过于降低索引叶子块的争用，减少热点块，提高系统性能。（3）.使用反向索引的

20、缺点 由于反向索引结构自身的特点，如果系统中经常使用范围扫描进行读取数据的话（例如在where子句中使用“between and”语句或比较运算符“>”“<”等），那么反向索引将不适用，因为此时会出现大量的全表扫描的现象，反而会降低系统的性能。有时候可以通过改写sql语句来避免使用范围扫描，例如where id between 12345 and 12347，可以改写为where id in(12345,12346,12347)，CBO会把这样的sql查询转换为where id=12345 or id=12346 or id=12347,这对反向索引也是有效的。（4）.通过一个小实

21、验简单演示一下反向索引的创建及修改1. SQL> select count(*) from t1; 2.   COUNT(*)  3. -  4.          0  5. SQL> select count(*) from t2;  6.   COUNT(*)  

22、;7. -  8.          0  9. SQL> select count(*) from t3;  10.   COUNT(*)  11. -  12.    2000000  13. SQL> select INDEX_NAME,INDEX_TYPE,T

23、ABLE_NAME from user_indexes;  14. INDEX_NAME                     INDEX_TYPE                

24、0; TABLE_NAME  15. - - -  16. PK_T2                          NORMAL/REV          

25、0;       T2  17. PK_T1                          NORMAL            

26、;          T1  表t1是主键是正常的主键，表t2的主键是反向主键。现在我把表t3的数据分别插入到表t1和表t21. SQL> set timing on;  2. SQL> set autotrace on;  3. SQL> insert /* +append */ into t1&#

27、160;select * from t3;  4. 已创建2000000行。  5. 已用时间:  00: 01: 42.83  6. 执行计划  7. -  8. Plan hash value: 4161002650  9. -  10. | Id  | Operation   

28、60;            | Name | Rows  | Bytes | Cost (%CPU)| Time     |  11. -  12. |   0 | INSERT STATEMENT  

29、60;      |      |  2316K|   485M| 19014   (1)| 00:03:49 |  13. |   1 |  LOAD TABLE CONVENTIONAL | T1   | 

30、      |       |            |          |  14. |   2 |   TABLE ACCESS FU

31、LL      | T3   |  2316K|   485M| 19014   (1)| 00:03:49 |  15. -  16. Note  17. -  18.    - dynamic sampling used for

32、0;this statement (level=2)  19. 统计信息  20. -  21.       12305  recursive calls  22.      538835  db block gets  23.      20393

33、7  consistent gets  24.       83057  physical reads  25.   428323528  redo size  26.         688  bytes sent via SQL*Net

34、 to client  27.         614  bytes received via SQL*Net from client  28.           3  SQL*Net roundtrips to/from client&

35、#160; 29.           2  sorts (memory)  30.           0  sorts (disk)  31.     2000000  rows processed 

36、60;32. SQL> commit;  33. 提交完成。  34. 已用时间:  00: 00: 00.04  35. SQL> insert /* +append */ into t2 select * from t3;  36. 已创建2000000行。  37. 已用时间:  00: 02:

37、60;02.63  38. 执行计划  39. -  40. Plan hash value: 4161002650  41. -  42. | Id  | Operation                | Name | Rows

38、60; | Bytes | Cost (%CPU)| Time     |  43. -  44. |   0 | INSERT STATEMENT         |      |  2316K|  

39、; 485M| 19014   (1)| 00:03:49 |  45. |   1 |  LOAD TABLE CONVENTIONAL | T2   |       |       |    &#

40、160;       |          |  46. |   2 |   TABLE ACCESS FULL      | T3   |  2316K|   485M

41、| 19014   (1)| 00:03:49 |  47. -   48. Note  49. -  50.    - dynamic sampling used for this statement (level=2)  51. 统计信息  52. -  53.   

42、;     7936  recursive calls  54.     6059147  db block gets  55.      158053  consistent gets  56.       56613 

43、0;physical reads  57.   790167468  redo size  58.         689  bytes sent via SQL*Net to client  59.         614  b

44、ytes received via SQL*Net from client  60.           3  SQL*Net roundtrips to/from client  61.           2  sorts (

45、memory)  62.           0  sorts (disk)  63.     2000000  rows processed  64. SQL> commit;  65. 提交完成。  66. 已用时间:  00: 00: 0

46、0.01  可以看见：由于反向索引的数据块比较分散了后，db block gets要稍微高一些。热块的争用有所缓解，consistent gets有所下降，从203937下降到158053，减少了45884次。redo size 也变多了！再来做查询，来看看他们的区别。1. SQL> set autotrace traceonly;  2. SQL> select OBJECT_NAME from t1 where id = 100;

47、  3. 已用时间:  00: 00: 00.06  4. 执行计划  5. -  6. Plan hash value: 1141790563  7. -  8. | Id  | Operation              &

48、#160;    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |  9. -  10. |   0 | SELECT STATEMENT         &#

49、160;  |       |     1 |    79 |     0   (0)| 00:00:01 |  11. |   1 |  TABLE ACCESS BY INDEX

50、0;ROWID| T1    |     1 |    79 |     0   (0)| 00:00:01 |  12. |*  2 |   INDEX UNIQUE SCAN     &

51、#160;   | PK_T1 |     1 |       |     0   (0)| 00:00:01 |  13. -  14. Predicate Information (identified by operation

52、0;id):  15. -  16.    2 - access("ID"=100)  17. 统计信息  18. -  19.           0  recursive calls  20.        

53、;   0  db block gets  21.           4  consistent gets  22.           3  physical reads  23.   

54、        0  redo size  24.         434  bytes sent via SQL*Net to client  25.         416  bytes 

55、;received via SQL*Net from client  26.           2  SQL*Net roundtrips to/from client  27.           0  sorts (memory)&#

56、160; 28.           0  sorts (disk)  29.           1  rows processed  30. SQL> select OBJECT_NAME from t1 where i

57、d > 100 and id < 200;  31. 已选择99行。  32. 已用时间:  00: 00: 01.10  33. 执行计划  34. -  35. Plan hash value: 1249713949  36. -  37. | Id  | Operatio

58、n                   | Name  | Rows  | Bytes | Cost (%CPU)| Time     |  38. -  39. |   0

59、60;| SELECT STATEMENT            |       |    99 |  7821 |     1   (0)| 00:00:01 |  40. | 

60、  1 |  TABLE ACCESS BY INDEX ROWID| T1    |    99 |  7821 |     1   (0)| 00:00:01 |  41. |*  2 |   I

61、NDEX RANGE SCAN          | PK_T1 |    99 |       |     1   (0)| 00:00:01 |  42. -  43. Predicate

62、0;Information (identified by operation id):  44. -  45.    2 - access("ID">100 AND "ID"<200)  46. Note  47. -  48.    - dynamic sampling us

63、ed for this statement (level=2)  49. 统计信息  50. -  51.           9  recursive calls  52.           0  db block&

64、#160;gets  53.         140  consistent gets  54.         189  physical reads  55.        2356  redo size 

65、 56.        2656  bytes sent via SQL*Net to client  57.         482  bytes received via SQL*Net from client  58.    

66、;       8  SQL*Net roundtrips to/from client  59.           0  sorts (memory)  60.           0  

67、;sorts (disk)  61.          99  rows processed  62.   63. SQL> select OBJECT_NAME from t2 where id = 100;  64. 已用时间:  00: 00: 00.05&

68、#160; 65. 执行计划  66. -  67. Plan hash value: 1480579010  68. -  69. | Id  | Operation                   | Name  

69、;| Rows  | Bytes | Cost (%CPU)| Time     |  70. -  71. |   0 | SELECT STATEMENT            |     

70、60; |     1 |    79 |     0   (0)| 00:00:01 |  72. |   1 |  TABLE ACCESS BY INDEX ROWID| T2    | 

71、60;   1 |    79 |     0   (0)| 00:00:01 |  73. |*  2 |   INDEX UNIQUE SCAN         | PK_T2 | &#

72、160;   1 |       |     0   (0)| 00:00:01 |  74. -  75. Predicate Information (identified by operation id):  76. -  77.   

73、; 2 - access("ID"=100)  78. 统计信息  79. -  80.           1  recursive calls  81.           0  db block 

74、;gets  82.           4  consistent gets  83.           1  physical reads  84.           0&

75、#160; redo size  85.         434  bytes sent via SQL*Net to client  86.         416  bytes received via SQL*Net from cli

76、ent  87.           2  SQL*Net roundtrips to/from client  88.           0  sorts (memory)  89.       

77、    0  sorts (disk)  90.           1  rows processed  91. SQL> select OBJECT_NAME from t2 where id > 100 and id <

78、60;200;  92. 已选择99行。  93. 已用时间:  00: 00: 04.39  94. 执行计划  95. -  96. Plan hash value: 1513984157  97. -  98. | Id  | Operation        &

79、#160;| Name | Rows  | Bytes | Cost (%CPU)| Time     |  99. -  100. |   0 | SELECT STATEMENT  |      |   336 | 

80、26544 |  8282   (1)| 00:01:40 |  101. |*  1 |  TABLE ACCESS FULL| T2   |   336 | 26544 |  8282   (1)| 00:01:40 |  102. -

81、  103. Predicate Information (identified by operation id):  104. -  105.    1 - filter("ID">100 AND "ID"<200)  106. Note  107. -  108.    -

82、 dynamic sampling used for this statement (level=2)  109. 统计信息  110. -  111.          29  recursive calls  112.          

83、; 1  db block gets  113.       60187  consistent gets  114.       30335  physical reads  115.        5144  redo size  116.        2656  bytes sent via SQL*Net to client