第四章空间存储和索引.ppt

Chapter4: Spatial Storage and Indexing;Learning Objectives;Physical model in 3 level design?;What is a physical data model?;Concepts in a physical data model;An interesting fact about physical data model;Physical data model for SDBMS;Common assumptions for SDBMS physical model;Common Spatial Queries and Operations;Scope of discussion;Learning Objectives;4.1 Storage:Disk and Files-- Storage Hierarchy in Computers;Measure of efficiency;基本存储;物理存储介质：基本存储;物理存储介质：基本存储;物理存储介质：在线存储;物理存储介质：脱机存储;物理存储介质：脱机存储;4.1.1 Secondary Storage Hardware: Disk Drives;磁盘存储物理特性;Disk drive concepts;Using Disk Hardware Efficiently;4.1.2 Buffer Management;虚拟内存;4.1.3 Software view of Disks: Fields, Records and File;Mapping Records and files to Disk;;相关概念;Learning Objectives;4.1.4 File Structures - selected file operations;4.1.4 File Structure--Common File Structures;4.1.4 File Structures: Heap(堆 );File Structure : Hash(散列);4.1.4 File Structures: Ordered;4.1.5 Spatial File Structures: Clustering;SDBMS支持三种聚类;空间聚类技术;用置换规则如何统一生成 Z-Curve;Example of Z-values;Hilbert Curve;Hilberlt曲线 转换 ;Calculating Hilbert Values (Optional Topic);磁盘访问的度量;Z曲线和Hilbert曲线的聚类效率;区域处理 ;把一幅2n×2n的图像压缩成线性四叉树的过程;;6．访问方法的算法;空间连接：;采用Z序的B树;Learning Objectives;What is an index?;索引--加快检索速度;Classifying indexes;桶;Attribute data types and Indices;4.2.1 Grid Files; 1. Use non-uniform grids (Fig. 4.14) Linear scale store row and column boundaries 2. Allow sharing of disk sectors across grid cells;Grid Files;4.2.2 R-Tree Family;Spatial Objects with R-Tree;Properties of R-trees;Spatial Objects with R-Tree;R+tree;Learning Objectives;4.3 Trends;4.3.2 Trends - Concurrency support;4.3.3 Trends: Join Index;Spatial Join-index Details;Summary;§空间索引（Spatial Index）与空间检索;一、索引文件;1、索引非顺序文件;1、索引非顺序文件;维护;排序费时；文件大时索引速度较慢。 解决方法——建立多级索引;2、索引顺序文件;索引顺序文件的索引机制;2、索引顺序文件;二、格网索引（Grid Index);格网索引实例;三、其他空间索引;3、四叉树索引;4、R树;5、R+树;6、CELL树;四、空间检索;四、空间检索