搜索
第1页共15页学号：课程设计题目B*树索引学院计算机科学与信息工程学院专业金融信息化服务外包班级学生姓名指导教师2015年12月27日第2页共15页重庆工商大学课程设计成绩评定表学院：计信学院班级：学生姓名：学号：项目分值优秀(100x≥90)良好(90x≥80)中等(80x≥70)及格(70x≥60)不及格(x60)评分参考标准参考标准参考标准参考标准参考标准学习态度15学习态度认真，科学作风严谨，严格保证设计时间并按任务书中规定的进度开展各项工作学习态度比较认真，科学作风良好，能按期圆满完成任务书规定的任务学习态度尚好，遵守组织纪律，基本保证设计时间，按期完成各项工作学习态度尚可，能遵守组织纪律，能按期完成任务学习马虎，纪律涣散，工作作风不严谨,不能保证设计时间和进度技术水平与实际能力25设计合理、理论分析与计算正确，实验数据准确，有很强的实际动手能力、经济分析能力和计算机应用能力，文献查阅能力强、引用合理、调查调研非常合理、可信设计合理、理论分析与计算正确，实验数据比较准确，有较强的实际动手能力、经济分析能力和计算机应用能力，文献引用、调查调研比较合理、可信设计合理，理论分析与计算基本正确，实验数据比较准确，有一定的实际动手能力，主要文献引用、调查调研比较可信设计基本合理，理论分析与计算无大错，实验数据无大错设计不合理，理论分析与计算有原则错误，实验数据不可靠，实际动手能力差，文献引用、调查调研有较大的问题创新10有重大改进或独特见解，有一定实用价值有较大改进或新颖的见解，实用性尚可有一定改进或新的见解有一定见解观念陈旧论文(计算书、图纸)撰写质量50结构严谨，逻辑性强，层次清晰，语言准确，文字流畅，完全符合规范化要求，书写工整或用计算机打印成文；图纸非常工整、清晰结构合理，符合逻辑，文章层次分明，语言准确，文字流畅，符合规范化要求，书写工整或用计算机打印成文；图纸工整、清晰结构合理，层次较为分明，文理通顺，基本达到规范化要求，书写比较工整；图纸比较工整、清晰结构基本合理，逻辑基本清楚，文字尚通顺，勉强达到规范化要求；图纸比较工整内容空泛，结构混乱，文字表达不清，错别字较多，达不到规范化要求；图纸不工整或不清晰指导教师评定成绩：指导教师签名：年月日第3页共15页课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目:B*树索引已知技术参数和设计要求：a)时间要求为14周~18周。b)开发工具不限（oracle/sqlplus）。c)开发平台不限（Linux）。d)集成开发环境不限。e)所用数据库不限（Oracle10g）。f)说明文档要求符合学校课程设计文档规范。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）B*树索引。(1)什么是B*树(2)B*索引的组织结构(3)索引键压缩(作用及结构)(4)反向键索引(作用及结构)(5)降序索引(作用及结构)时间安排：1、研究分析什么是B*树，和同学讨论联系实际，历时2天。2、研究分析B*索引的组织结构，历时2天。3、研究分析索引键压缩，反向键索引，降序索引，历时4天。4、编写相关文档，历时2天。5、Oracle大型数据库课程设计文档的最后检查与修订，历时1天指导教师签名：年月日第4页共15页目录1.什么是B*树........................................................................................................................................................52.B*索引的组织结构.............................................................................................................................................63.索引键压缩(作用及结构)...................................................................................................................................64.反向键索引(作用及结构)...................................................................................................................................8（1）.反向索引应用场合.............................................................................................................................9（2）.使用反向索引的优点………………………………………………………………………………..9（3）.使用反向索引的缺点………………………………………………………………………………..9（4）.通过一个实验简单演示一下反向索引的创建及修改……………………………………………145.降序索引（作用及结构）...............................................................................................................................146.总结...................................................................................................................................................................157.参考资料...........................................................................................................................................................15第5页共15页1.什么是B*树B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）。如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针，所以，B*树分配新结点的概率比B+树要低，空间使用率更高。B*树索引就是我们说的“传统”索引，这是数据库中最常用的一类索引结构。其实现与二叉查找树类似，目标是减少oracle查找数据的时间。如果在一个数字列上有一个索引，那么理论上结构应该是这样的（图1）：图1具体B*结构示意图这个树最底层是叶子节点，包含索引键以及一个rowid（指向索引行）。叶子节点上面的称为分支块，用于在结构中实现导航。例如：想在索引中找到值42，从树顶开始查找进入左分支，查找这个块，发现需要找的数据在“42...50”的叶子节点中。另外，叶子节点之间是双向链表结构。也就是查找区间数第6页共15页据很容易，比如这样的条件：wherexbetween20and300。oracle只要刚开始找到大于或等于20的记录所在的叶子节点，接着往下扫描，找到大于或者等于300的块。这期间可能会跨叶子节点扫描，由于叶子节点之间是双向链表，故很容易实现跨叶子节点扫描。B*树有一个特点：所有的叶子节点都在同一层，也就是无论你查找哪一条数据，需要执行的I/O数据是一样的。一般的B*树都是2或者3层。无论这个表有多少行数据，这样查找一条数据只需要2,3个I/O操作。2.B*索引的组织结构一般的B*树结构如图2所示。图2B*结构示意图最底层的数据块被称为叶子结点，叶子结点中包含了索引键值和其所对应的ROWID。其它的数据块被称为分支块,可用于定位相应的叶子结点。同时叶子结点之间也存在一个双向链表，当对某个索引进行范围扫描时,可通过叶子结点之间的双向链表来进行检索而不用通过分支结点。每个索引最少有一个叶子结点，一个叶子结点中可包含多行索引数据。B*树索引中所有的叶子结点都应在同一层中,此层的高度也即称为这个索引的高度，因此可以说索引是高度平衡的。B*树索引最大的层次为24层，一个索引中最多只能包含32个字段列。每个键的长度根据不同版本的数据块大小的不同而不同。分支块结点存储的是指向其下层结点的指针，每一个索引都有一个根结点，根结点所在的数据块在索引段中紧随段头信息所在的数据块。整个索引的层次被称为索引的高度，可通过数据库中视图index_stat中的字段height查出，分支结点的层次被称为blevel，可在数据字典dba_indexes中的字段blevel查出，需对索引进行分析才可计算出索引的高度和blevel的值，即analyzeindexindex_namevalidatestructure。索引的高度是由索引的分支结点的个数决定的，而索引分支结点的个数又是由索引键值的长度和索引叶子结点的个数决定的。Oracle数据库中的最小逻辑单元是数据库数据块，其大小由数据库初始化参数DB_BLOCK_SIZE所决定。所有的索引数据和表数据都是以数据块为单位存放的，同时每个索引数据块会存放相应的头信息。3.索引键压缩(作用及结构)信息检索系统中的两个主要数据结构:词典及倒排索引。下面将介绍对这两个数据结构的各种压缩技术,这些技术对于构建高效的IR系统非常关键。进行压缩的一个优点显而易第7页共15页见:它能够节省磁盘空间。要达到1∶4的压缩比是非常容易的,也就是说可以降低75%的索引存储开销。索引压缩还有两个隐含的优点。第一是能增加高速缓存(caching)技术的利用率。在搜索系统中,词典中某些条目及其索引往往比其他条目及其索引的使用更频繁。例如：如果将一个频繁使用的查询词项t的倒排记录表放到高速缓存中,那么对仅由t构成的查询进行应答所需要的计算完全可以在内存中完成。如果采用压缩技术,那么高速缓存中就可以放更多的信息。当查询词项t的信息放在高速缓存时,处理查询t便不再需要进行磁盘操作,而只需将其倒排记录表在内存中解压缩即可。因此,我们能充分减少IR系统的应答时间。由于内存比磁盘更贵,所以,相对于磁盘空间的减少,采用高速缓存技术带来的速度提升是采用压缩技术的更主要的原因。第二个隐含的优点是,压缩能够加快数据从磁盘到内存的传输速度。高效的解压缩算法在现代硬件上运行相当快,这样将压缩的数据块传输到内存并解压所需要的总时间往往会比将未压缩的数据块传输到内存要快。举例来说,即使会增加在内存进行解压缩的开销,我们也可以通过加载一个小很多的压缩倒排记录表来减少I/O时间。因此,在大部分情况下,使用压缩倒排记录表的检索系统会比没用压缩的系统的运行速度要快。如果压缩的主要目的是为了节省磁盘空间,那么压缩算法的速度就不用特别考虑。但是,如果要提高高速缓存利用率和磁盘到内存的传输率,则解压缩的速度必须要快。【将词典看成单一字符串的压缩方法】采用定长方法来存储词项存在着明显的