(1)假设D是正整数的集合,而1由从0到n的证书构成,Q含有所有的点查询,即,有单独的(1},{2},…,(n},假设我们想用一个B+树来索引这个工作负载,其中每个页节点可以含有1个证书。该索引模式的块大小是多少?使用的块数为多少?
(2)索引模式S的存储冗余是含有I的一个元素的块的最大个数,题(1)中使用B+树的存储冗余是多少?
(3)在模式S下,Q中的一个查询的访问代价是满足该查询的最小块数。该查询的访问代价是其访问代价除以其理想访问代价,即[1Q|/B]。在题(1)中B+树索引下任意查询的访问代价是多少?访问代价又是多少?
(4)索引模式本身的访问开销是所有查询Q中的最大访问开销。说明这个值永远不会超过B.那么B+树模式的访问开销是多少呢?
(5)我们现在为路径索引定义一个工作负载。字段D={i:1是一个正整数},从直观上来说,这是所有对象标识的集合。一个实例可以是D的任何有限子集,为了定义Q,我们在1中的对象标识集上加上了一个树结构。因此,如果1中有n个标识我们就定义一个有n个节点的树T,并将每一个节点与1中的一个标识相关联。该树是有根的并且是有节点标签,其中节点标签来自一个标签的无限集合E。T的根有一个不同的标签root,现在,如果S是T上某一路径表达式的结果,则Q含有一个I中对象标识的子集S。我们只考虑简单路径表达式;即,形如PE= roots, I1s2l2.L的表达式,其中s是分隔符//或/,每一个1是来自集合E的一个标签。该表达式返回所有T中与PE匹配的路径上的节点对应的所有对象标识说明对于任一r,存在一个路径索引工作负载,使得对于任何有冗余的索引模式,r至多会有访问开销B
(3)在模式S下,Q中的一个查询的访问代价是满足该查询的最小块数。该查询的访问代价是其访问代价除以其理想访问代价,即[1Q|/B]。在题(1)中B+树索引下任意查询的访问代价是多少?访问代价又是多少?
(4)索引模式本身的访问开销是所有查询Q中的最大访问开销。说明这个值永远不会超过B.那么B+树模式的访问开销是多少呢?
(5)我们现在为路径索引定义一个工作负载。字段D={i:1是一个正整数},从直观上来说,这是所有对象标识的集合。一个实例可以是D的任何有限子集,为了定义Q,我们在1中的对象标识集上加上了一个树结构。因此,如果1中有n个标识我们就定义一个有n个节点的树T,并将每一个节点与1中的一个标识相关联。该树是有根的并且是有节点标签,其中节点标签来自一个标签的无限集合E。T的根有一个不同的标签root,现在,如果S是T上某一路径表达式的结果,则Q含有一个I中对象标识的子集S。我们只考虑简单路径表达式;即,形如PE= roots, I1s2l2.L的表达式,其中s是分隔符//或/,每一个1是来自集合E的一个标签。该表达式返回所有T中与PE匹配的路径上的节点对应的所有对象标识说明对于任一r,存在一个路径索引工作负载,使得对于任何有冗余的索引模式,r至多会有访问开销B
