数据库有关索引查找.pptx

空间聚类技术的特点 空间数据所处的空间——多维空间，没有天然顺序 磁盘——一维设备 多维空间——映射——一维空间 要求：距离不变 ——空间上邻近的元素——映射为——直线上接近的点， 一一对应。目前无完全理想的方法。 主要映射方法 Z序/曲线（Z-order） Hilbert曲线 格雷码（Gray code）;（1）Z曲线;（2）Hilbert曲线;（3）Z曲线的生成算法 读入空间对象点的x，y坐标——二进制表示 对二进制的x，y坐标的每一位，隔行扫描，形成一个由0，1组成的字符串 计算该二进制 字符串的十进制数值， 该十进制数——Z值 按Z值，由小到大， 连线——Z曲线;（4）Hilbert曲线算法 读入对象点的x，y坐标——二进制表示，n位 对二进制的x，y坐标的每一位，隔行扫描，形成一个由0，1组成的字符串（图a)） 将该字符串自左至右分成2位长的串si，i = 1, 2, …, n 给每个2位长的串规定一个十进制数di，如：规定“00”为0， “10”为3，“11”为2 （图b)） 对于上步合并后的数组，对左第一位值，若： j = 0 ——把后面所有的1变成3，3变成1 j = 3 ——把后面所有的0变成2，2变成0（图c)） 计算变换后的二进制串的十进制数，按数值大小，由小到大连线——Hilbert曲线（图d)）;（5）磁盘访问的度量 影响磁盘访问次数的因素 磁盘页面容量 分割算法——大的区域分割成小的区域 插入顺序 空间填充曲线聚类性能的度量标准：对一片连续空间范围网格的访问涉及尽量少间断的磁盘页面 聚类——越集中，性能越佳 连续行程——越长，性能越佳 每个网格点的平均散列单元数——越少，性能越佳;（6）区域处理 N维空间中的区域——转换成——点：对空间对象的MBR使用2N次Z曲线 一个区域——划分成——多个片/块（block）——四叉树递归分割 每个块——一个Z值。大块有大块的Z值，小块有小块的Z值;（6）访问方法的算法 使用Z序方法——利用空间对象的Z值——访问空间对象 点查询 ——根据给定的点的Z值， 二分法：排序文件 B树有哪些信誉好的足球投注网站算法：基于Z值的B树索引 范围查询 将查询范围——翻译成——一组Z值 有哪些信誉好的足球投注网站待查询的数据区域的Z值，与查询范围的Z值比较，若：匹配，则：查询到 假设：2个区域r1（z1）、r2（z2） 2种情况： 若：z1是z2的前缀，则：r1完全包含r2 若：否，则： r1与r2不相交;最近邻居查询 ——使用：Z序的B树 计算查询点pi的z值 从B树中找最近的z值及其数据点pj 计算pi与pj之间的距离r 以pi为中心、r为半径进行范围查询，得到半径r内的所有点 计算上述查询范围内所有点与查询点pi的距离，找出距离最近的点——最近邻居;空间连接 设：S——湖（空间对象集），R——铁路（空间对象集） 查询：找出所有穿过湖的铁路 将集合S的元素转化为Z值表，排序 将集合R的元素转化为Z值表，排序 合并2个Z值表 利用Z值确定是否交叠——同范围查询 采用Z序的B树进行空间连接的缺陷： 若：网格结构不一致，则：索引的分区不能直接连接 Z序具有很长的对角线跨越，连接这些跨越的连续Z值在X-Y坐标系中距离很大 改进：使用Hilbert曲线;练习;4.2 空间索引 索引文件 ——用来提高数据文件查询效率的辅助文件 使用：折半查找算法 索引文件的组成 2个域： 主码域 数据文件的页面地址 二级索引文件;主索引 ——数据文件的记录按主码域排序，索引文件中只需保存数据文件的每个磁盘页面的第一个主码域的值;一维有哪些信誉好的足球投注网站码的索引;一维有哪些信誉好的足球投注网站码的索引：B树;一维有哪些信誉好的足球投注网站码的索引：B+树;多维索引;空间索引结构 使用：桶——对应：磁盘页面，外存储器中存放多个记录的“数据块”为“桶”。（扇区是磁盘最小单元，每次读写字节数必须是一个扇区的整数倍；数据块（磁盘页面）是逻辑上的概念，由操作系统定义的，它的大小是一个扇区的整数倍；桶是从文件结构出发，根据记录的大小，把文件上一条或多记录刚好存放到一个磁盘块上，一个桶对应一个磁盘块） 桶区域——包含存储在桶中全部空间对象的一部分空间 点数据结构：桶区域通常不相交，一个点只属于一个桶 矩形数据结构：桶区域可能相交（矩形在空间上可能相交） 提供空间索引的2种方法： 加入专门的外部空间数据结构，为空间属性提供如B树一样的索引 使用空间填充曲线，将空间对象映射到一维空间，使空间对象存储在标准的一维索引中（如B树）;4.2.1 网格文件 固定网格结构