5. Cost-Performance Comparisons with Other Access Methods(2)
Assume we are dealing with an arbitrary indexing structure. Recall that we calculated the number of entries in the Acct-ID||Timestamp index by assuming they were generating 1000 entries per second over a 20 day period of accumulation with eight hour days. Given index entries 16 bytes in length (4 bytes for the Acct-ID, 8 bytes for the timestamp, and 4 bytes for the History row RID) this implies 9.2 GBytes of entries or about 2.3 million 4 KByte pages of index, even if there is no wasted space. None of these conclusions are subject to change because of the specific choice of index method. A B-tree will have a leaf level with a certain amount of wasted space together with upper level directory nodes, whereas an extendible hash table will have a somewhat different amount of wasted space and no directory nodes, but both structures must contain 9.2 GBytes of entries as calculated above. Now to perform an insert of a new index entry into an index structure, we need to calculate the page on which the entry is to be inserted and make sure that page is memory resident. The question naturally arises: Are newly inserted entries generally placed in an arbitrary position among all 9.2 GBytes of index entries that are already present? The answer, for most classical acccess method structures, is Yes.
假设我们正在处理一个任意索引结构。回想一下,我们计算Acct-ID||Timestamp索引中的条目数量,方法是假设它们在20天的累积周期(每天8小时)中每秒生成1000个条目。给定长度为16字节的索引项(4字节用于Acct-ID, 8字节用于时间戳,4字节用于History行RID),这意味着9.2 g字节的条目或大约230万4kbyte页的索引,即使没有浪费空间。这些结论都不会因为索引方法的具体选择而改变。B-tree的叶级和上层目录节点将浪费一定数量的空间,而可扩展哈希表将有不同数量的空间浪费和没有目录节点,但这两种结构都必须包含9.2 g的条目,如上所述。现在,为了执行将新索引项插入索引结构的操作,我们需要计算要插入该条目的页面,并确保该页面驻留在内存中。问题很自然地出现了:新插入的条目通常被放置在已经存在的所有9.2 gb索引条目中的任意位置吗?对于大多数经典的访问方法结构,答案是肯定的。(有道翻译)
todo:自己翻译,仔细看