基本操作 Scan 口读取文件中所有的记录 Search with equality selection 口读取文件中满足某一相等条件的记录 Search with range selection 口读取文件中满足区间条件的记录 Insert ¤将特定记录插入文件 Delete 口将特定记录从文件中删除
36 基本操作 ◼ Scan ❑ 读取文件中所有的记录 ◼ Search with equality selection ❑ 读取文件中满足某一相等条件的记录 ◼ Search with range selection ❑ 读取文件中满足区间条件的记录 ◼ Insert ❑ 将特定记录插入文件 ◼ Delete ❑ 将特定记录从文件中删除
堆文件 Scan 口代价为BD+RC) Search with equality selection 口如事先知道只有一个结果,则为0.5B(D+RC),否则同Scan Search with range selection 口代价为B(D+RC) Insert 口2D+C(数据加在关系的最后面) Delete aD+C(数据已经在内存中,可用rid中的 page id访问)
37 堆文件 ◼ Scan ❑ 代价为B(D+RC) ◼ Search with equality selection ❑ 如事先知道只有一个结果，则为0.5B(D+RC),否则同Scan ◼ Search with range selection ❑ 代价为B(D+RC) ◼ Insert ❑ 2D+C(数据加在关系的最后面) ◼ Delete ❑ D+C(数据已经在内存中，可用rid中的page id访问)
排过序的文件 Scan 口代价为BD+RC) Search with equality selection 口代价为Dlog2B+Clog2R(没有重复的情况,且对査询属性排序) Search with range selection a同上 Insert 口B(D+RC)(数据是连续存放的情况) Delete 口B(D+RC)(数据是连续存放的情况) 38
38 排过序的文件 ◼ Scan ❑ 代价为B(D+RC) ◼ Search with equality selection ❑ 代价为Dlog2B+Clog2R(没有重复的情况，且对查询属性排序) ◼ Search with range selection ❑ 同上 ◼ Insert ❑ B(D+RC)(数据是连续存放的情况) ◼ Delete ❑ B(D+RC)(数据是连续存放的情况)
Hashed的文件 文件被分解为筐 Bucket) ■通过一个HaSh函数找到相应的筐 需要考虑溢出的情况 Bucket1 Hash函数 Bucket2 Bucket3 Bucket4 Bucket5 39
39 Hashed的文件 ◼ 文件被分解为筐(Bucket) ◼ 通过一个Hash函数找到相应的筐 ◼ 需要考虑溢出的情况 Hash函数 Bucket1 Bucket2 Bucket3 Bucket4 Bucket5
Hashed的文件 Scan 口代价为125B(D+RC(由于在文件中保存了一定的空闲) Search with equality selection 口代价为HD+0.5RC(只有一个结果) Search with range selection 口代价为125B(D+RC) Insert a代价为2D Delete a代价为C+D 40
40 Hashed的文件 ◼ Scan ❑ 代价为1.25B(D+RC)(由于在文件中保存了一定的空闲) ◼ Search with equality selection ❑ 代价为H+D+0.5RC(只有一个结果) ◼ Search with range selection ❑ 代价为1.25B(D+RC) ◼ Insert ❑ 代价为2D ◼ Delete ❑ 代价为C+D