例子和相关参数 o Sailors(sid: integer, sname: string, rating: integer, ag e real) o Reserves(sid: integer, bid: integer, day: date, rname: string) 每个 reserve记录长为40个字节,一页100条记录, 共1000页 每个 sailors记录长为50个字节,一页80条记录, 共500页 只考虑MO的页数 ●忽略结果的大小,因为同一个操作的不同实现方 法都一样
例子和相关参数 ⚫ Sailors(sid:integer,sname:string,rating:integer,ag e:real) ⚫ Reserves(sid:integer, bid:integer, day:date,rname:string) ⚫ 每个reserve记录长为40个字节，一页100条记录， 共1000页 ⚫ 每个sailors记录长为50个字节，一页80条记录， 共500页 ⚫ 只考虑I/O的页数 ⚫ 忽略结果的大小，因为同一个操作的不同实现方 法都一样
选择操作 ●讨论目标: O Select from Reserves where r name= Joe ○对应的查询代数操作为 name= Joe (R) ●没有索引,数据不排序 ○需要扫描整个表 ○代价是1000次○操作 ○选择率差,代价比较大
选择操作 ⚫讨论目标： Select * from Reserves R where R.name=‘Joe’ 对应的查询代数操作为：name=‘Joe’(R) ⚫没有索引，数据不排序 需要扫描整个表 代价是1000次I/O操作 选择率差，代价比较大
选择操作 ●没有索引,数据排序 ○采用折半查找的方法 ○代价是O(og21000),约为10次WO操作 ○选择率高,代价比较小 O如约束是at5,则首先找到5所在的位置,然后 从5开始遍历 ○一般情况下数据的排序往往是和索引相关的
选择操作 ⚫没有索引，数据排序 采用折半查找的方法 代价是O(log21000)，约为10次I/O操作 选择率高，代价比较小 如约束是attr>5，则首先找到5所在的位置，然后 从5开始遍历 一般情况下数据的排序往往是和索引相关的
选择操作 ●使用B+树索引 ○查询方法 ●首先找到约束数据所在的位置 ●从相应的 data entry开始向后逐个检测直到找到所有满 足条件的 data entry 根据 data entry找到相应的元组 代价分析 ●一般找到起始的叶节点只需要2-3次读写 ●主要代价在于满足条件的记录数和索引的是否是簇聚 的
选择操作 ⚫使用B+树索引 查询方法 ⚫首先找到约束数据所在的位置 ⚫从相应的data entry开始向后逐个检测直到找到所有满 足条件的data entry ⚫根据data entry找到相应的元组 代价分析 ⚫一般找到起始的叶节点只需要2-3次读写 ⚫主要代价在于满足条件的记录数和索引的是否是簇聚 的
选择操作 使用B+树索引 ○如果索引是簇聚的,检测满足条件的元组的代价一般为 次O ○如果索引不是簇聚的,检测满足条件的元组的代价为满 足条件的元组的个数次WO,如果事先对涉及的 pageid进 行排序,则将减少O次数避免对同一页进行重复读 O假设查询条件改为 Frame<“c%”,则结果数为表的大小的 10% ●如果索引是簇聚的,则代价约为100次O操作 ●如果索引是不是簇聚的,则代价最坏为10000次O操作, pageid排序后最坏约为1000次1O操作 ○选择率高,代价比较小
选择操作 ⚫ 使用B+树索引 如果索引是簇聚的，检测满足条件的元组的代价一般为 一次 I/O 如果索引不是簇聚的，检测满足条件的元组的代价为满 足条件的元组的个数次I/O，如果事先对涉及的pageid进 行排序，则将减少I/O次数避免对同一页进行重复读 假设查询条件改为rname<“c%”，则结果数为表的大小的 10% ⚫如果索引是簇聚的，则代价约为100次I/O操作 ⚫如果索引是不是簇聚的，则代价最坏为10000次I/O操作， pageid 排序后最坏约为1000次I/O操作 选择率高，代价比较小