上海交通大学高级数据库课件陆朝俊ed6ch25解读.ppt

版本向量方案 基本思想: 每个宿主i 为它上面的文档d 的副本存储一个版本向量 – 版本号集合: 对其他每个可能更新d的宿主k 有一个元素 Vd,i [k] 当宿主i 更新文档d, 则将版本号Vd,i [i] 加1 文档d 在主机 i 和 j 的副本是不一致的, 若 文档 d 在 i 上的副本包含由宿主k (k 可与 i 相同)执行的更新, 该更新还没有传播到宿主j, 并且 d 在 j 的拷贝包含由宿主l (l 可与 j 相同)执行的更新,该更新还没有传播到宿主i 版本向量方案 (续) 当两个宿主 i 和 j 相互连接时, 它们交换更新文档从而都得到新版本. 交换文档之前,要先检查一致性: 如果两个宿主上的版本向量相同 (即对每个k, Vd,i [k] = Vd,j [k]), 则d 的副本完全一致. 如果版本向量不同且对每个k, Vd,i [k] ? Vd,j [k], 则文档d 在i 上的拷贝比在 j 上的拷贝老 即, 文档 d 在j 上的拷贝是通过对文档 d 在i 上的拷贝作了一次或多次更新后而得到的. i 利用j 的副本来替换它自己的副本(连同版本向量). 如果有一对宿主k 和 m 使得 Vd,i [k] Vd,j [k] 且 Vd,i [m] Vd,j [m], 则副本不一致,即在 d 上执行了两个或更多的独立的更新. 人工介入 版本向量方案(续) 版本向量方案 最早用于处理分布式文件系统的故障 移动计算环境类似于一个经常断开连接的分布式文件系统 也用于群件系统:周期性连接并交换文档 用于有复制的数据库系统: “文档” 可以是单个元组. 例如,移动设备和宿主都存储的数据.更新可发生在两处. 处理不一致更新一般很难. 经常需要手工干涉来合并更新. End 例:四叉树 PR四叉树:存储的是点; 空间划分是基于区域的, 而不是基于实际点集. 区域四叉树 区域四叉树存储阵列(栅格)信息. 若节点覆盖的区域中所有阵列元素值都相同, 则该节点是叶结点; 否则划分成四个相等区域, 该节点是内节点 每个节点对应于一个值的子阵列. 对应于叶节点的子阵列要么只包含单个阵列元素, 要么有多个具有相同值的阵列元素. 线段和多边形的索引 人们提出了k-d 树和四叉树的扩展来索引线段和多边形 线段和多边形可能跨越区域的分界线 需要将线段/多边形分割 同一线段/多边形可能需在多个叶节点处表示 存储和查询效率低下 R树简介 R树是B+-树的N维推广,适用于点,线,矩形及其他多边形的索引. 很多现代数据库系统都支持R树及其变种R+树和R*树. 基本思想: 将与B+树节点关联的一维区间的思想推广到N维区间, 即N维矩形. 我们只考虑二维的情况(N = 2) N 2时的推广是直接的,但R树只适合较小的N R树的定义 被索引的对象存储在叶节点上 每个节点都与一个边与坐标轴平行的矩形边界框相关联. 叶节点的边界框是包含所有存储于该叶节点的对象的最小矩形. 一个空间对象(任意形状)的边界框是包含它的最小矩形 叶节点也可以存储对象的边界框 非叶节点的边界框是包含它的所有子节点的边界框的最小矩形. 一个节点的边界框相当于它的父节点中的键值 一个节点的各子节点的边界框可以重叠 边界框有利于快速判断矩形区域是否重叠 R-树的存储效率比k-d树和四叉树好, 因为一个多边形只存储在一个节点上 例:R树 矩形(实线):表示空间对象 边界框(虚线):不同层次的边界框构成了R树 查找 给定p(点/区域),要查找与之重叠的数据项(空间对象),从根节点开始做以下步骤: 如果是叶节点, 输出键值与p相交的数据项. 否则,递归有哪些信誉好的足球投注网站当前节点的每一个其限定框与p重叠的子节点 在最坏情况下可能效率很低, 因为可能需要有哪些信誉好的足球投注网站多条路径 兄弟节点的边界框可能重叠 插入 为了插入一个数据项: 找到存储它的叶节点, 并将它加入该叶节点 为找到叶节点, 沿着其限定框包含该数据项的限定框的子节点(若有的话)下行, 否则沿着其限定框与数据项限定框具有最大重叠的子节点下行 通过分裂处理溢出(同B+ -树) 但分裂过程不同 (见下) 从叶节点向上调整限定框 分裂过程: 目标: 将溢出节点中的项分成两个集合, 使得限定框具有最小总面积 这是启发式. 其他如最小重叠也是可能的 寻求“最佳”分裂开销很大, 可用启发式 见后 分裂 二次分裂(Quadratic split): 将节点中的项如下划分到两个新节点 找出一对具有“最大间距”的项 即, 使得两者的限定框具有最大浪费空间(限定框面积 – 两项的面积之和) 将它们分别放入两个新节点 重复为两个新节点之一找出具有 “最大选择机会”的项, 并将该项放入该节点 项对一节点的选择机会是指如果它加入到另一节点中会导致限定框面积的增加量 当一半项已经加入到一个节点中