高明网站建设首选公司,石家庄网站推广排名,会员收费网站怎么做,深圳鸿天顺网站建设顺序文件上的索引#xff08;一#xff09;研究索引结构#xff0c;我们首先来考虑最简单的一种#xff1a;由一个称为数据文件的排序文件得到另一个称为索引文件的文件#xff0c;而这个索引文件由键-指针对组成。在索引文件中查找键K通过指针指向数据文件中查找键为K的记… 顺序文件上的索引一研究索引结构我们首先来考虑最简单的一种由一个称为数据文件的排序文件得到另一个称为索引文件的文件而这个索引文件由键-指针对组成。在索引文件中查找键K通过指针指向数据文件中查找键为K的记录。索引可以是“稠密的”即数据文件中每个记录在索引文件中都设有一个索引项索引也可以是“稀疏的”即数据文件中只有某些记录在索引文件中表示出来通常为每个数据块在索引文件中设一个索引项。1、顺序文件一种最简单的索引结构要求文件按索引的属性排序这样的文件称为顺序文件。当查找键是关系的主键时这种结构特别有用当然对关系的其他属性也可使用这种结构。图4-2所示为一个用顺序文件表示的关系。键以及几种不同的键术语“键”有几个涵义本书在适当的上下文中使用了“键”的不同涵义。你肯定对“键”用来表示“关系的主键”十分熟悉。这样的键用SQL定义。且需要关系满足在主键属性或属性组上不存在值相同的两个元组。在2.3.4节中我们学过“排序键”文件的记录据此排序。现在来看“查找键”已知在该属性组上的值需要通过索引查找具有相应值的元组。当“键”的涵义不清楚时尽量使用恰当的修饰词“主”、“排序”或“查找”。不过请注意在4.1.2节和4.1.3节中很多时候这三种键是同一涵义。在这个文件中元组按主键排序。这里假定主健是整数我们只列出了主键字段。同时我们还做了一个不代表典型情况的假定即每个存储块中只可存放两个记录。例如文件的第一个块中存放键值为10和20的两条记录。在这里和其他许多例子中我们使用10的连续倍数来做键值虽然实际中不会要求键值都是10的倍数或10的所有倍数都必须出现。2、稠密索引既然把记录排好了序我们就可以在记录上建立稠密索引。它是这样的一系列存储块块中只存放记录的键以及指向记录本身的指针指针就是如3.3节讨论的那样的地址。我们说这里的索引是“稠密的”因为数据文件中每个键在索引中都被表示出来。与此相比将在4.3节中讨论的“稀疏”索引通常在索引中只为每个数据块存放一个键。稠密索引文件中的索引块保持键的顺序与文件中的排序顺序一致。既然假定查找键和指针所占存储空间远小于记录本身我们就可以认为存储索引文件比存储数据文件所需存储块要少得多。当内存容纳不下数据文件但能容纳下索引文件时索引的优势尤为明显。这时通过使用索引文件我们每次查询只用一次I/O操作就能找到给定键值的记录。例4.1 图4-3所示为一个建立在顺序文件上的稠密索引该顺序文件的起始部分如图4-2所示。为了方便起见还是假定文件中记录的键值是10的倍数虽然实际中我们不能指望找到这样一个有规律的键值模式。我们还假定每个索引存储块只可存放四个键-指针对。在实际中我们会发现每个存储块能存放更多的键-指针对甚至是好几百个。第一个索引块存放指向前四个记录的指针第二个索引块存放指向接下来的四个记录的指针依此类推。出于将在4.1.6节讨论的原因实际中我们可能不希望装满所有的索引块。稠密索引支持按给定键值查找相应记录的查询。给定一个键值K我们先在索引块中查找K。当找到K后按照K所对应的指针到数据文件中寻找相应的记录。似乎在找到K之前我们需要检索索引文件的每个存储块或平均一半的存储块。然而由于有下面几个因素基于索引的查找比它看起来更为有效1索引块数量通常比数据块数量少。2由于键被排序我们可以使用二分查找法来查找K。若有n个索引块我们只需查找log2n个块。3索引文件可能足够小以致可以永久地存放在主存缓冲区中。要是这样的话查找键K时就只涉及主存访问而不需执行I/O操作。例4.2 假设一个关系有1000000个元组大小为4096字节的存储块可存放10个这样的元组那么这个关系所需的存储空间就要超过400MB因为太大而可能在主存中无法存放。然而要是关系的键字段占30字节指针占8字节加上块头所需空间那么我们可以在一个小大为4096字节的存储块中存放100个键-指针对。这样一个稠密索引就需要10000个存储块即40MB。我们就有可能为这样一个索引文件分配主存缓冲区不过要看主存的使用情况和主存的大小。进一步讲log210000大约是13因此采用二分查找法我们只需访问13~14个存储块就可以查找到给定键值。且由于二分查找法只检索所有存储块中一小部分是这样一些存储块它们位于1/2、1/4或3/4、1/8或3/8、5/8或7/8等等即使不能把整个索引文件存放到主存中我们也可以把这些最重要的存储块放到主存中这样检索任何键值所需的I/O次数都远小于14。索引块的定位假设存在一些定位索引块的机制根据索引可以查找到单个元组若是稠密索引或数据存储块若是稀疏索引。许多定位索引的机制可以使用。例如。假如索引较小我们可以将它存放到主存或磁盘的预留存储区中。假如索引较大则如我们在4.1.4节讲述的那样我样可以在索引上再建一级索引并将新的索引本身存放到某个固定的地方。对这一观点进行推广。最后就产生了4.3节中的B树在B树中我们只需要知道根索引块的位置。3、稀疏索引要是稠密索引太大我们可以使用一种称为稀疏索引的类似结构。它节省了存储空间但查找给定值的记录需更多的时间。如图4-4所示稀疏索引只为每个存储块设一个键-指针对。键值是每个数据块中第一个记录的对应值。例4.3 同例4.1一样假定数据文件已排序且其键值为连续的10的倍数直至某个较大的数。我们还继续假定每个存储块可存放四个键-指针对。这样第一个索引存储块中为前四个数据存储块的第一个键值的索引项它们分别是10、30、50和70。按照前面假定的键值模式第二个索引存储块中为第5~第8数据存储块的第一个键值的索引项它们分别是90、110、130和150。图中还列出第三个索引存储块存放的键值它们分别是假设的第九~第十二个数据存储块的第一个键值。例4.4 稀疏索引所需的索引存储块要比稠密索引少得多以例4.2中更接近实际的参数为例。由于有100000个数据存储块且每个索引存储块可存放100个键-指针对那么要是使用稀疏索引我们就只需要1000个索引存储块。现在索引的大小只剩下4MB这样大小的文件完全可能存到主存中。另一方面稠密索引不用去检索包含记录的块就可以回答下面形式的查询“是否存在键值为K的记录”。键K在索引中的存在足以保证数据文件中键值为K的记录的存在。当然如果使用稀疏索引对于同样的查询却需要执行I/O操作去检索可能存在键值为K的记录的块。在已有稀疏索引的情况下要找出键值为K的记录我们得在索引中查找键值小于或等于K的最大键值。由于索引文件已按键排序我们可以使用二分查找法来定位这个索引项然后根据它的指针找到相应的数据块。现在我们必须搜索这个数据块以找到键值为K的记录。当然数据块中必须有足够的格式化信息来标明其中的记录及记录内容。只要合适可以采用3.2节和3.4节中的任何技术。4、多级索引索引文件本身可能占据多个存储块正如我们在例4.2和例4.4中看到的那样。要是这些存储块不在我们知道能找到它们的某个地方比如指定的磁盘柱面那么就可能需要另一种数据结构来找到这些索引存储块。即便能定位索引存储块并且能使用二分查找法找到所需索引项我们仍可能需要执行多次I/O操作才能得到我们所需的记录。通过在索引上再建索引我们能够使第一级索引更为有效。图4-5对图4-4进行了扩展它是在图4-4的基础上增加二级索引得到的和前面一样我们假设使用10的连续倍数这一不常见的模式。按照同样想法我们可以在二级索引的基础上建立三级索引等等。然而这种做法有它的局限与其建立多级索引我们宁愿考虑使用在4.3节讲述的B树。在这个例子中一级索引是稀疏的虽然我们也可以选择稠密索引来作为一级索引。但是二级和更高级的索引必须是稀疏的因为一个索引上的稠密索引将需要和其前一级索引同样多的键-指针对因而也就需要同样的存储空间。因此二级稠密索引只是增加额外的结构而不会带来任何好处。例4.5 继续以例4.4中假设的关系来分析假定我们在一级稀疏索引上建立二级索引。由于一级稀疏索引占据1000个存储块且我们可以在一个存储块中存放100个键-指针对则只需要10个存储块来存放这个二级索引。10个存储块完全可以一直缓存在主存中。若是这样要查找给定键值K的记录可以先查看二级索引以找到小于或等于键值K的最大键值。根据这个最大键值对应的指针找到一级索引的某个存储块B通过这个存储块B我们就肯定能找到所需的记录。假若存储块B不在内存中我们就把存储块B读进内存这是我们所需的第一次I/O操作。在块B中查找小于或等于键值K的最大键值要是有键值为K的记录存在则通过块B中这一键值对应的指针就可以找到包含键值为K的记录的数据块。这个数据块需要又一次的I/O操作。这样我们只用两次I/O操作就完成了查询。oracle视频教程请关注:http://u.youku.com/user_video/id_UMzAzMjkxMjE2.html 转载于:https://blog.51cto.com/19880614/1309486
