1、第2部分 关系数据库系统实现第5章 数据库索引技术,高级数据库系统及其应用,2018年10月11日,2,第5章 数据库索引技术,几种文件组织方式的特性对比分析,5.1,索引技术基础,5.2,B+树索引,5.3,散列索引,5.4,位图索引,5.5,多维空间索引,5.6,2018年10月11日,3,5.1 几种文件组织方式的特性对比分析,5.1.1 文件的记录组织方式,5.1.2 各种文件组织方式的特性分析,2018年10月11日,4,5.1.1 文件的记录组织方式,堆文件(heap file) 排序文件(sorted file) 散列文件(hashed file) 以记录的某个属性值为参数，通过
2、特定散列函数求得有限范围内的一个值作为记录的存储地址(即页地址或桶号)。 用于计算散列的属性也称为散列键，它与搜索键具有类似的概念。,2018年10月11日,5,5.1.2 各种文件组织方式的特性分析,假设文件有B个数据页，每页有R个记录；平均读写1个页的时间为D，(CPU)处理一个记录的时间为C。对于散列文件组织，散列函数映射的时间为H。 分析时采用如下简单代价模型： I/O操作代价具有主导性。 DB缓冲区大小对DB操作有重要影响。为了行较全面的性能评价，分析时我们选择几种具有代表性的典型DB操作：,扫描(Scan) 等值搜索(Equality Search) 取文件中满足等值选择条件的所有
3、记录 包含满足条件记录的所有页须从磁盘读到主存。 范围搜索(Ranging Search) 插入(insert) 必须先定位新记录应插入的页，并将该页读入主存，在主存页中完成插入修改，然后，再将该页写回磁盘。 删除(delete) 如采用等值或范围条件选择删除记录，则操作过程与插入/范围搜索操作类似； 如直接给定删除记录rid，则可直接定位到记录所在页。,2018年10月11日,6,5.1.2.1 堆文件的操作特性分析,扫描 操作代价为B(D+RC) 等值搜索 假设:满足条件的记录只有一个, 平均需检查一半的页 操作代价取0.5DB 范围搜索必检查所有的页，操作代价B(D+RC) 插入 取文件
4、的最后页到主存，插入后，再写回磁盘 操作代价为2D+C 删除 不考虑记录被删除后的空间合并 操作代价为：搜索时间C+D 若已知rid，可直接定位到目标页，可省去搜索时间,2018年10月11日,7,5.1.2.2 排序文件的操作特性分析,扫描 操作代价为B(D+RC) 等值搜索 假设：满足条件的记录只有一个 可用二分法搜索，操作代价取D*log 2BC log 2R 若满足条件记录有多个，则该代价还应加上读取包含所有这些记录的若干个连续页。 范围搜索等值搜索代价matches 插入 插入后，需进行排序调整，假设需调整约一半的记录 插入操作的代价=等值搜索代价2*0.5B(D+RC)。 删除 如
5、果等值或范围删除条件，则代价与插入操作相同 若已知rid，可直接定位到目标页，可省去搜索时间,2018年10月11日,8,5.1.2.3 散列文件的操作特性分析,扫描 页空间通常只保持约80%的占用率，扫描的实际操作代价取1.25B(D+RC) 等值搜索 能非常有效支持等值选择 假设满足条件的记录只有一条且相应桶中没有溢出页，则等值搜索操作代价仅为H+D+0.5RC 范围搜索 需要扫描所有的页，操作代价1.25B(D+RC) 插入插入操作代价=等值搜索代价D+C 。 删除 对等值或范围选择删除，代价=搜索代价D+C 如果直接给定rid，则可省去搜索时间，代价= D+C,2018年10月11日,
6、9,各种文件组织方式的特性对比,2018年10月11日,10,5.2 索引技术基础,5.2.1 索引技术综述,5.2.2 顺序索引及其特性,5.2.3 创建索引语句,2018年10月11日,11,5.2.1 索引技术综述,索引 是一种能帮助我们有效找出满足指定条件记录rid的辅助数据结构，是一种特殊类型的记录文件。 索引记录 常被称为索引项(index entry) ，简记为k* 除了索引项按索引键值顺序组织的顺序索引外，也有按树结构(如B+树)和桶结构(散列)进行组织的索引。 RDBMS中，索引项可能具有的三种形式 （1）索引项k*是数据记录本身，无单独的索引文件。 这时数据文件可视为一种特
7、殊的数据文件组织，即散列文件 。 （2） ，有独立的索引文件。 （3），有独立的索引文件，且每个索引项中允许包含多个rid。,2018年10月11日,12,5.2.1 顺序索引及其特性,聚集与非聚集索引 聚集索引(clustered index)：指索引项的排序方式和数据文件记录排序方式一致的索引 稠密索引与稀疏索引 稠密索引：每个索引键值都对应有一索引项 稀疏索引：只为某些搜索键值建立索引项 多级索引 为处理索引项过多带来的索引性能下降问题，可以将索引文本本身当作一般顺序数据文件，在其上再建一个索引，即二级索引。 如果建立三级或更多级的索引，通常不如直接使用B树方便。 主索引与辅助索引 仅当
8、搜索键恰好是主码的索引时，索引称为主索引；,2018年10月11日,13,稠密索引与稀疏索引应用示例,2018年10月11日,14,多级索引应用示例,2018年10月11日,15,一种带有间接桶层的辅助索引结构,2018年10月11日,16,5.3 B+树,5.3.1 B+树概述,5.3.2 B+树操作,5.3.3 B+树的效率与实用化,2018年10月11日,17,5.3.1 B+树特点及约束（1）,B+树的基本特点 是传统B树的一种增强结构。采用一种平衡树来组织索引项。内节点用于搜索导向，叶节点用来存储数据项。 是一种动态的索引结构，其树大小会因数据项的多少而动态地增长或收缩。 每个树节点
9、用一个页来存储。 树操作(插入/删除)能保持树平衡。从根节点到任一个叶节点路径都是等长的。 B+树的阶数（通常以字母m表示） 指B+树中节点允许容纳的最大索引键值个数。,2018年10月11日,18,5.3.1 B+树特点及约束（2）,根节点/内节点格式化 除了根节点外，所有树节点都必须保持50%的占用率(即半满）。 一个含有j个索引键值的节点，必含有j+1个指针 节点内容格式“p0, K1, p1, , Kj, pj” ，其中，指针pi指向一个键值k落在Kin （简记为k*）的数据记录指针。 每个叶子节点与前后的叶子节点用双链连接在一起。,2018年10月11日,19,5.3.2.1 B+树
10、搜索算法（算法5.1),/主函数 func find (search-key-value K) returns nodePointer/给定搜索键值K，找所在的叶节点return tree-search (root, K); endfunc,2018年10月11日,20,B+树搜索算法（算法5.1),2018年10月11日,21,一个阶数m=4的B+树及其搜索示例,2018年10月11日,22,5.3.2.2 B+树插入算法（算法5.2),2018年10月11日,23,B+树插入算法（到达叶节点后的处理逻辑),2018年10月11日,24,B+树插入算法（非叶节点中分裂子节点处理逻辑),201
11、8年10月11日,25,插入算法应用示例演示,2018年10月11日,26,5.3.2.3 B+树删除算法（算法5.3),2018年10月11日,27,B+树删除算法（到达叶节点后的处理逻辑),2018年10月11日,28,B+树删除算法（处理有子节点被删除逻辑),2018年10月11日,29,删除算法应用示例演示,2018年10月11日,30,5.3.3 B树的效率与实用化,B+树索引的优势 虽然B+树付出了在内节点存储索引项的开销，但能获得排序文件的所有好处，且还能保持很好的插入、删除性能。 B树没有溢出页； 实用条件下，B树的每个页能容纳搜索键数可能很大，分裂/合并树节点的情况可能很少发
12、生。 按索引键值检索一条记录，典型只需要23次磁盘I/O。,2018年10月11日,31,5.3.3 B树的效率与实用化,B+树索引的优势 B+树重复键问题及其处理 当重复键很多时，可能会出现叶节点无法容纳具有给定键值所有记录项的情况。 常用处理方法 用溢出页来处理重复键值问题。 把重复键按一般非重复键一样处理，这时重复键项将出现在一个或连续的多个页节点中。 将rid值也作为搜索键的一个部分，这实际上相当于消除了重复键。,2018年10月11日,32,5.3.3 B树的效率与实用化,B+树索引的优势 B+树重复键问题及其处理 键值压缩处理（键压缩） 如果搜索键值很长，页中能存储的索引项数就很少
13、，树的宽度 (fan-out)也就小。 最大化fan-out以减小树的深度，对减少树操作磁盘I/O数非常重要。 键值压缩原理 只保留键的前缀。 为确保能保持一个索引项中键值的比较语义，在压缩一个项时，除考虑它相邻项键值外，还要考虑左、右子树中的最大键值。,2018年10月11日,33,5.3.3.3 批量加载数据集到B+树,数据项加入到B+树索引可能会遇到两种情形： 拟加入的数据记录集之前已建有B+树索引。这时，可利用标准的B+树插入算法，将数据项逐个加入数据集，同时更新相应的B+树索引。 拟加入的数据集上还没有B+树索引。 对于后者，为减少操作代价，常采用批量加载方法 实现批量加载数据集到B
14、+树的算法步 参见书本,P159,2018年10月11日,34,图5.6 批量加载B+树过程演示,2018年10月11日,35,批量加载数据集到B+树的代价分析,这个操作算法可归纳为三大步骤： 第一步，从一个记录集创建要插入到索引的数据项； 该步包括扫描关系记录集，并生成和写出相应的数据项。 其代价为(R+E)次I/Os R是记录集数据文件的总页数，E是包含数据项的总页数。 第二步，排序数据项； 外部排序含数据项的有E个页，保守估计需要3E次I/Os（参见6.1部分）。 第三步，从排序好的数据项中建立B+树索引。 该步的代价只是写出所有索引页的代价。 总代价为：R+4E+(B树索引节点数),2
15、018年10月11日,36,5.4 散列索引,5.4.1 静态散列存储表,5.4.2 可扩展的动态散列,5.4.3 线性散列表,2018年10月11日,37,散列存储技术概要,散列与散列函数 散列函数选择要求:随机分布好、易计算； 散列函数参数：查找键或散列键； 函数值：散列值 基于散列的存储结构 通常是每个散列值对应一个存储目标对象的桶(页/块) 散列值对应桶编号(如果散列值范围是0B-1，则桶总数为B)。 根据被散列对象键值，计算散列值，然后保存到相应的桶中； 当桶内对象不止一个时，按链连接起来，构成对象链。 存储到桶的对象，既可能是实际数据项或数据记录，也可以是数据记录指针;,2018年
16、10月11日,38,也称为辅存散列表； 桶数目固定，不随对象插入和删除变化； 桶中直接存放数据记录；插入新项时，如果空间不够（桶溢出） 属于同一个桶的多个页构成溢出页链； 桶内对象被删除，桶溢出页变为空时，也应将空溢出页删除。 辅存散列的效率 理想情况只需一次I/O； 非理想情况可能需要多次I/O（因存在对象链、溢出块链等情况）。,5.4.1 静态散列存储表,2018年10月11日,39,5.4.2 可扩展的动态散列（1）,静态散列一般通过增加溢出页来处理溢出问题。 如不希望增加溢出页，也可修改散列函数，将桶的数目扩大（如扩大一倍），然后重组数据文件。 但这种重组的代价可能很大： 需要读入n个
17、页，并写回2n个页。 克服这个问题的一个方法 引入一个仅存储桶指针的目录数组，用翻倍目录数组来取代翻倍数据桶数目； 由于每个目录项只含有一个桶指针，目录所需存储页一般很少，这样翻倍的代价就很小。 每次只分裂有溢出的桶。,2018年10月11日,40,5.4.2 可扩展的动态散列（2）,引入一散列函数h，将索引键值映射为二进制数，并解释最后的d个比特位。 d值是目录项的编码位数 目录项总数为2d个；d值加1目录项数将增加一倍。 d值也称全局位深度(the global bit-depth) 。 每个桶有一个局部位深度(the local bit-depth)。 在局部位深度为 的桶中，所存储数据
18、项对应散列值的后位取值都相同。 一般情况下，会有2d-个目录项指向这个桶；当=d时，只有一个目录项指向这个桶。最初，所有桶都有=d 。,2018年10月11日,41,当向一个已满的、局部位深度为的桶插入数据项时，就要分裂这个桶。 该桶及分裂产生的映像桶：+1； 如果+1d，则还需要增加目录的编码位数，即要对目录进行翻倍处理。 翻倍目录时，只需将原有的每个目录项分别复制产生1个对应的新目录项。 一个目录项和由它复制产生的新目录项，互称为“对应元素” “对应元素”开始时指向同一个桶，只是当桶分裂后，才分别指向原桶和原桶分裂映像。 可扩展散列存在的主要问题 当散列值分布不均匀或偏斜很大时，会导致目录
19、项数特别大和数据桶的空间利用率很低。 每次目录调整都是翻倍调整，目录大小扩展过快，调整不平滑。,5.4.2 可扩展的动态散列（3）,2018年10月11日,42,5.4.2 可扩展的动态散列（4）,2018年10月11日,43,5.4.2 可扩展的动态散列（5）,2018年10月11日,44,5.4.3 动态线性散列（1）,动态线性散列技术概要 也是一种动态散列存储技术，能随数据项的插入和删除，适时地对存储数据的桶数进行调整。 与可扩展散列相比，线性散列不需要存放数据桶指针的专门目录项，且能更自然处理数据桶已满的情况 但如果数据项键值散列后分布不均匀的偏斜度大，导致的问题可能会比扩展散列还严重
20、。,2018年10月11日,45,5.4.3 动态线性散列（2）,动态线性散列技术概要 理解线性散列技术（参考书本P63) 线性散列的技术特点 每次桶分裂的触发条件允许灵活选择 每次发生分裂的桶，总是由当前Next值来决定，与桶是否已满或溢出无关！ 为处理在已满桶中插入新数据项情况，需引入溢出块。 由于在一轮中，每个初始桶总会轮到一次分裂，所以，一般情况下，桶的溢出块数不会超过1块。,2018年10月11日,46,5.4.3 动态线性散列（4）,2018年10月11日,47,应用举例 例5.7 假设： 线性散列文件每个桶可存储4个数据项，初始时有4个桶，即N=4； 初始时，Level=0，Ne
21、xt=0； 采用“发生溢出插入”作为触发分裂的条件。 具体的初始状态如图5.9(a)中所示。试分析该线性散列中分别插入新项h(r)=43和h(r)=37后的情况。,5.4.3 动态线性散列（6）,初始轮，level=0, N=4，N0=N*2Level=4; d0=2； h0取h(k)的最后2个二进制位，作为桶索引指针； d1=d0+1，h1取h(k)的最后3个二进制位。,2018年10月11日,48,例5.7（续）,2018年10月11日,49,例5.7 （续）,2018年10月11日,50,5.5 位图索引,5.5.1 位图索引的结构,5.5.2 位图索引的应用,5.5.3 压缩位图,5.
22、5.4 压缩位图的游程解码操作,5.5.5 位图索引的维护,2018年10月11日,51,考虑一个共有n个记录的关系R和它的一个属性A，假设R的所有记录在A上只有m个的不同取值，v 1,v2, vm。 R在A上的位图索引 是一组位图向量； R.A的每个取值v j (j=1m)，分别对应一个位图向量bit_ vj ； 共有m个这样的位图向量。 bit_ vj是一宽度为n的二进制数，该数的第i位值 bit_vj i =1，如果第i条记录的R.A取值 vj ; bit_vj i =0，如果第i条记录的R.A取值 vj ;,5.5.1 位图索引的结构,2018年10月11日,52,位图索引示例（图5.
23、11),2018年10月11日,53,例5.10（续例5.9，多键码检索应用示例） 条件匹配查询 gender=f income-level=L2 ( r ) 范围查询 gender=f income-levelL2 ( r ),5.5.2 位图索引的应用,2018年10月11日,54,位图压缩的必要性 当用于建立位图索引的属性不同值数很多时，位图索引也可能会很大。 位图压缩技术的基本思想 对任何二进制数，我们总可以用i1个0、i2个0、i3个0、 来描述。由这个描述我们完全可以准确重构出这个二进制数。 但若直接对i1,i2,进行二进制编码，就会出现问题。 比如，对长度为3和1的两个字段，合成
24、为111。无法唯一解码还原位图向量。 解决这个问题的一个有效方案： 在数值i的二进制编码前，加上一个前缀码。 前缀码长度与值i的二进制编码长相同(令为j, j= log2i=4)，前缀码的取值模式为j-1个1后跟一个0。 对i=1特殊处理, 规定：i=0的编码为00，i=1的编码为01。 例如，对i=13：j=log213=4，编码为1110,1101。,5.5.3 压缩位图,例5.11 对位图0001000,0000110000,0000,0001进行编码； 解压缩码11101101001011 位图压缩的效率分析： 一个长度为i的码长为2 log2i，上限为2 log2n 因为最大向量个数
25、m4时，恒有2 nlog2n n2 成立，且n越大压缩效果越好。,2018年10月11日,55,5.5.4 压缩位图的游程解码操作,当要对两个压缩的位图向量运算时，必须先解码后运算。但不必先执行全部解码，可以结合运算的进行，一次一个段，即一次一个游程地交替解码。 例5.12 对两个压缩位图向量A:00110110(字段序列0,5)和B:11011111101101(字段序列为7,13)进行与运算，结果向量为C。,2018年10月11日,56,5.5.4 位图索引的维护,删除记录i 不调整位向量码长，仅将所有位图向量的第i位置为0； 同时将数据文件中对应的空间做删除标记； 插入新记录 所有位向量
26、在原来基础上补加1个0(对压缩码其实可不加)。 根据新记录的索引字段值，进行如下调整： 若是新出现的索引字段值，则增加1个位向量，并将该位向量的最后位改为1。 若是已有的索引字段值值，则找到该值的位向量，将该位向量的最后位(新加位)置为1。 位图索引属性值被修改,2018年10月11日,57,5.6 多维索引,5.6.1 多维空间索引技术综述,5.6.2 网格文件,5.6.3 R树,5.6.4 k-d树与四叉树,2018年10月11日,58,5.6.1 多维空间索引技术综述,4. 已建议的空间索引结构综述,3. 需要多维空间索引的应用简介,点数据(point data)与区域数据(region
27、 data),2. 空间数据及其查询的主要类型,1. 为什么需要多维空间索引,2018年10月11日,59,5.6.1.1 为什么需要多维空间索引（1）,例5.13 设有一个存放购买金首饰顾客信息记录的关系表Customers (age, salary)，假定在age和salary上分别建有B+索引。现考虑age建立B+树索引（仍是一维的）,2018年10月11日,60,5.6.1.1 为什么需要多维空间索引（2）,与B+树相比，多维或空间索引则往往利用某种空间关系（在空间中的相近性或邻近性）来组织数据项，如图5.12（b）所示。,2018年10月11日,61,5.6.1.2 空间数据及其查询
28、的主要类型,（一）空间数据的主要类型 （1）空间点数据 基本特点 只有位置，没有大小、边界，不占空间。 常见点数据类型 光栅数据(raster data。 多维特征向量(feature vector。 （2）区域数据 同时具有位置和边界的空间延展。 存储在DB中的区域数据，通常是一些用来逼近实际对象形体的系列简单几何体。,2018年10月11日,62,空间查询(spatial queries)的主要类型,范围查询(range queries) 空间范围查询通常关联着一个区域，并要求返回与目标区域范围重叠(overlap)或位于目标区域内的、指定类型的所有区域对象。 最邻近点查询(nearest
29、-neighbor queries) 要求找出离指定点最近的某些对象。例如，查询“找距某位置最近的10个城市”。 在多媒体数据处理中，这种查询显得特别重要。 空间连接查询(spatial join queries) 典型例子包括“找相互间距离不超过200公里的城市组对”，“找靠近某区域（如一个湖泊）的所有城市” 部分(维)查询 只指定部分维的值，查找匹配这些维值的所有对象；,2018年10月11日,63,基于范围查询的最邻近点查询实现算法,2018年10月11日,64,5.6.1.3 需要多维空间索引的应用简介,数据仓库的数据立方体,地理信息系统(GIS),CAD/CAM系统,多媒体信息处理,
30、2018年10月11日,65,在数据仓库中,通常需要建立一种称为“数据立方体”的多维数据结构,以更好支持决策分析。 例如，一个全国性连锁店，可能记录每一笔销售，包括销售时间、销售地区和商品的种类等。 事实数据事实表；可能影响这些销售事实数据的各因子，如时间、地区和商品类型等属性，作为不同的观察维度维表。 将所有维属性区段组合想象为一个个多维盒式单元，每个事实量（如销售量、销售额等）想象为存储在这些多维盒单元中的一个量。 本质上，可将事实表中每个元组视该空间的一个点。分析人员可按某些维对数据进行分组，并通过聚合操作对这些分组进行汇总。,5.6.1.3 数据仓库的数据立方体,2018年10月11日
31、,66,GIS被广泛用来处理各种空间数据，包括点、线、二维/三维-区域。 例如，一幅地图中，可能同时包含小目标（点）、河流/公路（线），以及城市/湖泊（区域）等。 GIS能自然提出所有空间查询类型，它必须能有效管理二维、三维数据集, 必须能有效处理空间点数据和区域数据。 当前许多对象数据库系统的都已能很好支持常见的GIS类应用。,5.6.1.3 地理信息系统(GIS),2018年10月11日,67,5.6.1.3 CAD/CAM系统,这类系统中通常要存储和处理大量的空间对象。类似GIS，这类系统中也必须存储和处理空间点/区域数据。 范围查询和空间连接查询可能是这类应用中最常见的查询。 CAM/
32、CAD也是对象数据库系统发展的一个主要动因。,2018年10月11日,68,多媒体涵盖诸如图像、文本和各种类型时间序列数据（音频/视频）等各类对象，也需要空间管理方式。 在多媒体数据库(multimedia databases)中，使用象“查找与特定对象相似的所有对象”这类相似查询可能极为普遍。 回答相似查询的一个通行方法是首先映射/变换多媒体对象到特征向量点，将查找相似对象问题转换为关于特征向量点集的最小邻近点查询问题。,5.6.1.3 多媒体信息处理,2018年10月11日,69,基于内容的图像检索技术,医疗/生物图像数据库 可能要存储大量数字化的二维/三维图像，如X-射线或MRI图像，形
33、成相对完整的、涵盖各种案例的样本图像库； 可基于图像相似匹配技术，处理新采集图像的模式识别问题。 基于指纹数据库，进行给定指纹的匹配搜索，处理指纹识别问题。 基于人脸图像数据库，进行给定人脸的匹配搜索。 视频剪辑数据库。在视频DB中，搜索有场景变化的特别帧，或搜索包含特别对象的视频帧序列，来跟踪处理运动对象。 存储文本文档集，并处理“在文档集中搜索包含相似主题文档”等有关问题。,以上应用,本质上都要处理相似图像的匹配/识别问题。,2018年10月11日,70,5.6.1.4 已建议的空间索引结构综述,建议了许多空间索引结构。 有些索引结构主要是为满足空间数据点检索需要而设计的； 以处理点数据为
34、主的索引结构包括网格文件、hB树、kd树、点四叉树(point quad trees)和SR树。 也有些能自然处理区域数据。而能自然处理区域数据的索引结构则包括区域四叉树(region quad trees)、R树和SKD树等。,2018年10月11日,71,5.6.2 网格索引结构（1）,例5.14 设有一个存放顾客购买金首饰记录的关系表(age,salary)。为使问题简化，我们假设该关系只有顾客年龄和月薪两个属性。 -实例数据中有12个顾客，相关记录被表示成下列的年龄-薪水对：(26,0.6) (45,0.6) (51,0.75) (51,1)(51,1.28)(70,1.30) (85
35、,1.4) (30,2.6) (26,4.0) (45,3.5)(51,2.75)(60,2.6),2018年10月11日,72,5.6.2 网格索引结构（2）,2018年10月11日,73,5.6.2 网格索引结构（3）,网格数组的每个单元(Cell)含有一个指向桶的指针，每个桶可以是一个页或页组，桶中直接存放记录。为了节省空间，网格的多个单元可以指向同一个桶。 网格文件的插入算法 举例：在图5.16网格中，插入记录(70, 3.5K) 。 有关步骤请参见书本 P177-178 网格文件对多维查询支持及性能 对指定点的查找，若无溢出块页，仅需1次I/O； 部分匹配：可能需要查找桶矩阵的某行或
36、某列的所有桶，I/O数可能很大； 范围查询：检查与范围区域有相交的所有桶；,2018年10月11日,74,R-树也是一种平衡树结构，其中被索引的多边形存储在叶节点上(这一点很象B+树)。 每个树节点(叶节点/内节点)都对应有一个平行于坐标轴的矩形边界框。 叶节点 负责存储位于其内的所有被索引多边形，边界框是一个能涵盖其内所有存储对象的最小矩形。 内节点 存储其每个子节点的边界框和指向各子节点的指针。 R树的基本操作：查找、删除和插入,5.6.3 R树,2018年10月11日,75,R树的两种视图,2018年10月11日,76,向R树中插入一个多边形(令其边框为target_PB)我们需选择一个
37、叶节点存放该多边形。 理想的情况是，我们能找到一个叶节点：它仍有空的项目空间，而且它的边界框包含该多边形的边界框。 也可能不存在这样节点；即使存在，找到它也是非常昂贵，因为不可能从根向下一次遍历就找到它。 在每个内部节点我们可能发现多个子节点边界框包含target_PB，而每个这样的子节点都要搜索。 可借助一种启发式的算法，来完成R树的插入任务。,5.6.3 R树-插入算法,2018年10月11日,77,考虑一维数据点的索引： 树结构(如二叉树或B-树)都是通过不断划分来分割空间的。 k-d树(k维搜索树)是早期用来建立多维空间索引的一种简单树形结构。 每个节点将一个空间划分为两个子空间。 划
38、分首先通过树顶层节点的一个维进行，然后在紧接的下一个层节点上用另一个维进行划分，以此类推。 k-d树数据结构特点（参见书本P181-182),5.6.4 KD树,2018年10月11日,78,5.6.4 KD树-示例,2018年10月11日,79,部分匹配查询 如果给定某属性的值，那么，当处在恰好是按该属性划分的层结点时，只需考察一个方向的子结点；否则要考察两个方向的子结点。 范围查询 如范围跨越结点划分值时，需考察两个方向的子结点树。 最邻近查询 可通过多次的范围查询来实现。 主要存在问题 每结点占用1个页,空间利用率低； 查询路径可能会很长；解决方案： 采用多分枝内结点(但这已不是k-d树了)； 聚集多个内结点到一个页,5.6.4 KD树-对多维查询支持,2018年10月11日,80,四叉树(quadtrees)是另一种组织二维空间数据索引存储的方法。 四叉树的每个节点关联到空间的一个矩形区 顶层节点关联整个目标空间， 每个节点有四个子节点关联到该节点所代表矩形区的四个象限。 叶节点有0个或多个不超过最大数的数据项数。 如果超过了指定的最大数据项数，叶节点转为节点，并进行四等分象限划分。,5.6.5 四叉树,
