第5章数据库索引技术

《第5章数据库索引技术》由会员分享，可在线阅读，更多相关《第5章数据库索引技术（80页珍藏版）》请在装配图网上搜索。

1、LOGO高级数据库系统及其应用高级数据库系统及其应用2023年2月11日2第第5 5章章 数据库索引技术数据库索引技术几种文件组织方式的特性对比分析几种文件组织方式的特性对比分析5.1索引技术基础索引技术基础5.2B+树索引树索引5.3散列索引散列索引5.4位图索引位图索引5.5多维空间索引多维空间索引5.62023年2月11日35.1 几种文件组织方式的特性对比分析几种文件组织方式的特性对比分析5.1.1 文件的记录组织方式 5.1.2 各种文件组织方式的特性分析2023年2月11日45.1.1 文件的记录组织方式文件的记录组织方式v堆文件(heap file)v排序文件(sorted fi

2、le)v散列文件散列文件(hashed file)以记录的某个属性值为参数，通过特定散列函数求得以记录的某个属性值为参数，通过特定散列函数求得有限范围内的一个值作为记录的存储地址有限范围内的一个值作为记录的存储地址(即页地址即页地址或桶号或桶号)。用于计算散列的属性也称为散列键，它与搜索键具有用于计算散列的属性也称为散列键，它与搜索键具有类似的概念。类似的概念。2023年2月11日55.1.2 各种文件组织方式的特性分析各种文件组织方式的特性分析v假设文件有假设文件有B个数据页，每页有个数据页，每页有R个记录；平均个记录；平均读写读写1个页的时间为个页的时间为D，(CPU)处理一个记录的处理一

3、个记录的时间为时间为C。对于散列文件组织，散列函数映射的。对于散列文件组织，散列函数映射的时间为时间为H。v分析时采用如下简单代价模型：分析时采用如下简单代价模型：I/O操作代价具有主导性。DB缓冲区大小对DB操作有重要影响。v为了行较全面的性能评价，分析时我们选择几种为了行较全面的性能评价，分析时我们选择几种具有代表性的典型具有代表性的典型DB操作操作：v 扫描扫描(Scan)v 等值搜索等值搜索(Equality Search)取文件中满足等值选择条件的所有记录取文件中满足等值选择条件的所有记录 包含满足条件记录的所有页须从磁盘读到主存。包含满足条件记录的所有页须从磁盘读到主存。v 范围搜

4、索范围搜索(Ranging Search)v 插入插入(insert)必须先定位新记录应插入的页，并将该页读入主存，必须先定位新记录应插入的页，并将该页读入主存，在主存页中完成插入修改，然后，再将该页写回磁盘。在主存页中完成插入修改，然后，再将该页写回磁盘。v 删除删除(delete)如采用等值或范围条件选择删除记录，则操作过程与如采用等值或范围条件选择删除记录，则操作过程与插入插入/范围搜索范围搜索操作类似；操作类似；如直接给定删除记录如直接给定删除记录rid，则可直接定位到记录所在页。，则可直接定位到记录所在页。2023年2月11日65.1.2.1 堆文件的操作特性分析堆文件的操作特性分析

5、v 扫描扫描 操作代价为操作代价为B(D+RC)v 等值搜索等值搜索 假设假设:满足条件的记录只有一个满足条件的记录只有一个,平均需检查一半的页平均需检查一半的页 操作代价取操作代价取0.5DBv 范围搜索必检查所有的页，操作代价范围搜索必检查所有的页，操作代价B(D+RC)v 插入插入 取文件的最后页到主存，插入后，再写回磁盘取文件的最后页到主存，插入后，再写回磁盘 操作代价为操作代价为2D+Cv 删除删除 不考虑记录被删除后的空间合并不考虑记录被删除后的空间合并 操作代价为：搜索时间操作代价为：搜索时间C+D 若已知若已知rid，可直接定位到目标页，可省去搜索时间，可直接定位到目标页，可省

6、去搜索时间2023年2月11日75.1.2.2 排序文件的操作特性分析排序文件的操作特性分析v 扫描 操作代价为B(D+RC)v 等值搜索 假设：满足条件的记录只有一个假设：满足条件的记录只有一个 可用二分法搜索，操作代价取可用二分法搜索，操作代价取D*log 2BC log 2R 若满足条件记录有多个，则该代价还应加上读取包含若满足条件记录有多个，则该代价还应加上读取包含所有这些记录的若干个连续页。所有这些记录的若干个连续页。v 范围搜索等值搜索代价matches v 插入 插入后，需进行排序调整，假设需调整约一半的记录插入后，需进行排序调整，假设需调整约一半的记录 插入操作的代价插入操作的

7、代价=等值搜索代价等值搜索代价2*0.5B(D+RC)。v 删除 如果等值或范围删除条件，则代价与插入操作相同如果等值或范围删除条件，则代价与插入操作相同 若已知若已知rid，可直接定位到目标页，可省去搜索时间，可直接定位到目标页，可省去搜索时间2023年2月11日85.1.2.3 散列文件的操作特性分析散列文件的操作特性分析v 扫描 页空间通常只保持约80%的占用率，扫描的实际操作代价取1.25B(D+RC)v 等值搜索 能非常有效支持等值选择能非常有效支持等值选择 假设满足条件的记录只有一条且相应桶中没有溢出页，假设满足条件的记录只有一条且相应桶中没有溢出页，则等值搜索操作代价仅为则等值搜

8、索操作代价仅为H+D+0.5RC v 范围搜索 需要扫描所有的页，操作代价需要扫描所有的页，操作代价1.25B(D+RC)v 插入插入操作代价=等值搜索代价D+C。v 删除 对等值或范围选择删除，代价对等值或范围选择删除，代价=搜索代价搜索代价D+C 如果直接给定如果直接给定rid，则可省去搜索时间，代价，则可省去搜索时间，代价=D+C 2023年2月11日9各种文件组织方式的特性对比各种文件组织方式的特性对比2023年2月11日105.2 索引技术基础索引技术基础5.2.1 索引技术综述 5.2.2 顺序索引及其特性5.2.3 创建索引语句2023年2月11日115.2.1 索引技术综述索引

9、技术综述 v 索引 是一种能帮助我们有效找出满足指定条件记录是一种能帮助我们有效找出满足指定条件记录rid的辅的辅助数据结构，是一种特殊类型的记录文件。助数据结构，是一种特殊类型的记录文件。v 索引记录 常被称为索引项常被称为索引项(index entry)，简记为，简记为k*除了索引项按索引键值顺序组织的顺序索引外，也有除了索引项按索引键值顺序组织的顺序索引外，也有按树结构按树结构(如如B+树树)和桶结构和桶结构(散列散列)进行组织的索引。进行组织的索引。v RDBMS中，索引项可能具有的三种形式（1）索引项）索引项k*是数据记录本身，无单独的索引文件。是数据记录本身，无单独的索引文件。这时

10、数据文件可视为一种特殊的数据文件组织，即散列文件这时数据文件可视为一种特殊的数据文件组织，即散列文件。（2），有独立的索引文件。，有独立的索引文件。（3），有独立的索引文件，且每个索引，有独立的索引文件，且每个索引项中允许包含多个项中允许包含多个rid。2023年2月11日125.2.1 顺序索引及其特性顺序索引及其特性 v聚集与非聚集索引聚集与非聚集索引 聚集索引聚集索引(clustered index)：指索引项的排序方式和指索引项的排序方式和数据文件记录排序方式一致的索引数据文件记录排序方式一致的索引 v稠密索引与稀疏索引稠密索引与稀疏索引 稠密索引：每个索引键值都对应有一索引项稠密索引

11、：每个索引键值都对应有一索引项 稀疏索引：只为某些搜索键值建立索引项稀疏索引：只为某些搜索键值建立索引项v多级索引多级索引 为处理索引项过多带来的索引性能下降问题，可以为处理索引项过多带来的索引性能下降问题，可以将索引文本本身当作一般顺序数据文件，在其上再将索引文本本身当作一般顺序数据文件，在其上再建一个索引，即二级索引。建一个索引，即二级索引。如果建立三级或更多级的索引，通常不如直接使用如果建立三级或更多级的索引，通常不如直接使用B树方便。树方便。v主索引与辅助索引主索引与辅助索引仅当搜索键恰好是主码的索引时，索引称为主索引；仅当搜索键恰好是主码的索引时，索引称为主索引；2023年2月11日

12、13稠密索引与稀疏索引应用示例稠密索引与稀疏索引应用示例2023年2月11日14多级索引应用示例多级索引应用示例2023年2月11日15一种带有间接桶层的辅助索引结构一种带有间接桶层的辅助索引结构 2023年2月11日165.3 B+树树5.3.1 B+树概述 5.3.2 B+树操作5.3.3 B+树的效率与实用化2023年2月11日175.3.1 B+树特点及约束（树特点及约束（1）vB+树的基本特点树的基本特点 是传统B树的一种增强结构。采用一种平衡树来组织索引项。内节点用于搜索导向，叶节点用来存储数据项。是一种动态的索引结构，其树大小会因数据项的多少而动态地增长或收缩。每个树节点用一个页

13、来存储。树操作(插入/删除)能保持树平衡。从根节点到任一个叶节点路径都是等长的。vB+树的阶数（通常以字母树的阶数（通常以字母m表示）表示）指指B+树中节点允许容纳的最大索引键值个数树中节点允许容纳的最大索引键值个数。2023年2月11日185.3.1 B+树特点及约束（树特点及约束（2）v 根节点根节点/内节点格式化内节点格式化 除了根节点外，所有树节点都必须保持除了根节点外，所有树节点都必须保持50%的占用率的占用率(即半满）。即半满）。一个含有一个含有j个索引键值的节点，必含有个索引键值的节点，必含有j+1个指针个指针 节点内容格式节点内容格式“p0,K1,p1,Kj,pj”，其中，指针

14、，其中，指针pi指向一指向一个键值个键值k落在落在Kin Ki+1范围的子树。范围的子树。m阶阶B+树的非叶节点至多只能有树的非叶节点至多只能有m+1个子节点；个子节点；内节点至少要有内节点至少要有 m/2+1个子节点；个子节点；根节点至少要有根节点至少要有2个子节点个子节点 v 叶节点格式化叶节点格式化 至多包含m个数据项，至少包含(m+1)/2个数据项；每个项既可以直接存放实际数据记录，也可以是形式为（简记为k*）的数据记录指针。每个叶子节点与前后的叶子节点用双链连接在一起。2023年2月11日195.3.2.1 B+树搜索算法（算法树搜索算法（算法5.1)/主函数主函数func find

15、(search-key-value K)returns nodePointer /给定搜索键值给定搜索键值K，找所在的叶节点，找所在的叶节点 return tree-search(root,K);endfunc2023年2月11日20B+树搜索算法（算法树搜索算法（算法5.1)2023年2月11日21一个阶数一个阶数m=4的的B+树及其搜索示例树及其搜索示例 2023年2月11日225.3.2.2 B+树插入算法（算法树插入算法（算法5.2)2023年2月11日23B+树插入算法（到达叶节点后的处理逻辑树插入算法（到达叶节点后的处理逻辑)2023年2月11日24B+树插入算法（非叶节点中分裂子

16、节点处理逻辑树插入算法（非叶节点中分裂子节点处理逻辑)2023年2月11日25插入算法应用示例演示插入算法应用示例演示2023年2月11日265.3.2.3 B+树删除算法（算法树删除算法（算法5.3)2023年2月11日27B+树删除算法（到达叶节点后的处理逻辑树删除算法（到达叶节点后的处理逻辑)2023年2月11日28B+树删除算法（处理有子节点被删除逻辑树删除算法（处理有子节点被删除逻辑)2023年2月11日29删除算法应用示例演示删除算法应用示例演示2023年2月11日305.3.3 B树的效率与实用化 vB+树索引的优势树索引的优势 虽然B+树付出了在内节点存储索引项的开销，但能获得

17、排序文件的所有好处，且还能保持很好的插入、删除性能。B树没有溢出页；实用条件下，B树的每个页能容纳搜索键数可能很大，分裂/合并树节点的情况可能很少发生。按索引键值检索一条记录，典型只需要23次磁盘I/O。2023年2月11日315.3.3 B树的效率与实用化 vB+树索引的优势树索引的优势vB+树重复键问题及其处理树重复键问题及其处理 当重复键很多时，可能会出现叶节点无法容纳当重复键很多时，可能会出现叶节点无法容纳具有给定键值所有记录项的情况。具有给定键值所有记录项的情况。常用处理方法常用处理方法 用溢出页来处理重复键值问题。用溢出页来处理重复键值问题。把重复键按一般非重复键一样处理，这时重复

18、键项把重复键按一般非重复键一样处理，这时重复键项将出现在一个或连续的多个页节点中。将出现在一个或连续的多个页节点中。将将rid值也作为搜索键的一个部分，这实际上相当于值也作为搜索键的一个部分，这实际上相当于消除了重复键。消除了重复键。2023年2月11日325.3.3 B树的效率与实用化 vB+树索引的优势树索引的优势vB+树重复键问题及其处理树重复键问题及其处理v键值压缩处理（键压缩）键值压缩处理（键压缩）如果搜索键值很长，页中能存储的索引项数就如果搜索键值很长，页中能存储的索引项数就很少，树的宽度很少，树的宽度(fan-out)也就小。也就小。最大化最大化fan-out以减小树的深度，对减

19、少树操作以减小树的深度，对减少树操作磁盘磁盘I/O数非常重要。数非常重要。键值压缩原理键值压缩原理 只保留键的前缀只保留键的前缀。为确保能保持一个索引项中键值的比较语义，在压为确保能保持一个索引项中键值的比较语义，在压缩一个项时，除考虑它相邻项键值外，还要考虑左、缩一个项时，除考虑它相邻项键值外，还要考虑左、右子树中的最大键值。右子树中的最大键值。2023年2月11日335.3.3.3 批量加载数据集到批量加载数据集到B+树树v数据项加入到数据项加入到B+树索引可能会遇到两种情形：树索引可能会遇到两种情形：拟加入的数据记录集之前已建有拟加入的数据记录集之前已建有B+树索引。这树索引。这时，可利

20、用标准的时，可利用标准的B+树插入算法，将数据项逐树插入算法，将数据项逐个加入数据集，同时更新相应的个加入数据集，同时更新相应的B+树索引。树索引。拟加入的数据集上还没有拟加入的数据集上还没有B+树索引。树索引。v对于后者，为减少对于后者，为减少操作代价，常采用批量加载方法v实现批量加载数据集到实现批量加载数据集到B+树的算法步树的算法步 参见书本,P1592023年2月11日34图图5.6 批量加载批量加载B+树过程演示树过程演示 2023年2月11日35批量加载数据集到批量加载数据集到B+树的代价分析树的代价分析这个操作算法可归纳为三大步骤：这个操作算法可归纳为三大步骤：第一步，从一个记录

21、集创建要插入到索引的数据项；第一步，从一个记录集创建要插入到索引的数据项；该步包括扫描关系记录集，并生成和写出相应的数该步包括扫描关系记录集，并生成和写出相应的数据项。据项。其代价为其代价为(R+E)次次I/Os R是记录集数据文件的总页数，是记录集数据文件的总页数，E是包含数据项的总页数。是包含数据项的总页数。第二步，排序数据项；第二步，排序数据项；外部排序含数据项的有外部排序含数据项的有E个页，保守估计需要个页，保守估计需要3E次次I/Os（参见（参见6.1部分）。部分）。第三步，从排序好的数据项中建立第三步，从排序好的数据项中建立B+树索引。树索引。该步的代价只是写出所有索引页的代价。该

22、步的代价只是写出所有索引页的代价。v总代价为：总代价为：R+4E+(B树索引节点数树索引节点数)2023年2月11日365.4 散列索引散列索引5.4.1 静态散列存储表 5.4.2 可扩展的动态散列5.4.3 线性散列表 2023年2月11日37散列存储技术概要散列存储技术概要v 散列与散列函数散列与散列函数 散列函数选择要求散列函数选择要求:随机分布好、易计算；随机分布好、易计算；散列函数参数：查找键或散列键；散列函数参数：查找键或散列键；函数值：散列值函数值：散列值v 基于散列的存储结构基于散列的存储结构 通常是每个散列值对应一个存储目标对象的桶通常是每个散列值对应一个存储目标对象的桶(

23、页页/块块)散列值对应桶编号散列值对应桶编号(如果散列值范围是如果散列值范围是0B-1，则桶总数为，则桶总数为B)。根据被散列对象键值，计算散列值，然后保存到相应的桶中；根据被散列对象键值，计算散列值，然后保存到相应的桶中；当桶内对象不止一个时，按链连接起来，构成对象链。当桶内对象不止一个时，按链连接起来，构成对象链。存储到桶的对象，既可能是实际数据项或数据记录，也存储到桶的对象，既可能是实际数据项或数据记录，也可以是数据记录指针可以是数据记录指针;2023年2月11日38v也称为辅存散列表；v桶数目固定，不随对象插入和删除变化；v桶中直接存放数据记录；插入新项时，如果空间不够（桶溢出）属于同

24、一个桶的多个页构成溢出页链；属于同一个桶的多个页构成溢出页链；桶内对象被删除，桶溢出页变为空时，也应将空溢出桶内对象被删除，桶溢出页变为空时，也应将空溢出页删除。页删除。v辅存散列的效率 理想情况只需一次理想情况只需一次I/O；非理想情况可能需要多次非理想情况可能需要多次I/O（因存在对象链、溢出块（因存在对象链、溢出块链等情况）。链等情况）。5.4.1 静态散列存储表静态散列存储表2023年2月11日395.4.2 可扩展的动态散列（可扩展的动态散列（1）v静态散列一般通过增加溢出页来处理溢出问题。静态散列一般通过增加溢出页来处理溢出问题。如不希望增加溢出页，也可修改散列函数，将桶的数目如不

25、希望增加溢出页，也可修改散列函数，将桶的数目扩大（如扩大一倍），然后重组数据文件。扩大（如扩大一倍），然后重组数据文件。但这种重组的代价可能很大：但这种重组的代价可能很大：需要读入需要读入n个页，并写回个页，并写回2n个页。个页。v克服这个问题的一个方法克服这个问题的一个方法 引入一个仅存储桶指针的目录数组，用翻倍目引入一个仅存储桶指针的目录数组，用翻倍目录数组来取代翻倍数据桶数目；录数组来取代翻倍数据桶数目；由于每个目录项只含有一个桶指针，目录所需存储由于每个目录项只含有一个桶指针，目录所需存储页一般很少，这样翻倍的代价就很小。页一般很少，这样翻倍的代价就很小。每次只分裂有溢出的桶。每次只分

26、裂有溢出的桶。2023年2月11日405.4.2 可扩展的动态散列（可扩展的动态散列（2）v引入一散列函数引入一散列函数h，将索引键值映射为二进制数，将索引键值映射为二进制数，并解释最后的并解释最后的d个比特位。个比特位。vd值是目录项的编码位数值是目录项的编码位数 目录项总数为目录项总数为2d个；个；d值加值加1目录项数将增加一倍。目录项数将增加一倍。d值也称值也称全局位深度全局位深度(the global bit-depth)。v每个桶有一个局部位深度每个桶有一个局部位深度(the local bit-depth)。在局部位深度为在局部位深度为 的桶中，所存储数据项对应散列值的的桶中，所存

27、储数据项对应散列值的后后位取值都相同。位取值都相同。一般情况下，会有一般情况下，会有2d-个目录项指向这个桶；当个目录项指向这个桶；当=d时，时，只有一个目录项指向这个桶。最初，所有桶都有只有一个目录项指向这个桶。最初，所有桶都有=d。2023年2月11日41v 当向一个已满的、局部位深度为当向一个已满的、局部位深度为的桶插入数据项时，就要的桶插入数据项时，就要分裂这个桶。分裂这个桶。该桶及分裂产生的映像桶：该桶及分裂产生的映像桶：+1；如果如果+1d，则还需要增加目录的编码位数，即要对目，则还需要增加目录的编码位数，即要对目录进行翻倍处理。录进行翻倍处理。v 翻倍目录时，只需将原有的每个目录

28、项分别复制产生翻倍目录时，只需将原有的每个目录项分别复制产生1个个对应的新目录项。对应的新目录项。一个目录项和由它复制产生的新目录项，互称为一个目录项和由它复制产生的新目录项，互称为“对应对应元素元素”“对应元素对应元素”开始时指向同一个桶，只是当桶分裂后，开始时指向同一个桶，只是当桶分裂后，才分别指向原桶和原桶分裂映像。才分别指向原桶和原桶分裂映像。v可扩展散列存在的主要问题可扩展散列存在的主要问题 当散列值分布不均匀或偏斜很大时，会导致目录项数特当散列值分布不均匀或偏斜很大时，会导致目录项数特别大和数据桶的空间利用率很低。别大和数据桶的空间利用率很低。每次目录调整都是翻倍调整，目录大小扩展

29、过快，调整每次目录调整都是翻倍调整，目录大小扩展过快，调整不平滑。不平滑。5.4.2 可扩展的动态散列（可扩展的动态散列（3）2023年2月11日425.4.2 可扩展的动态散列（可扩展的动态散列（4）2023年2月11日435.4.2 可扩展的动态散列（可扩展的动态散列（5）2023年2月11日445.4.3 动态线性散列（动态线性散列（1）v动态线性散列技术概要动态线性散列技术概要 也是一种动态散列存储技术，能随数据项的插也是一种动态散列存储技术，能随数据项的插入和删除，适时地对存储数据的桶数进行调整。入和删除，适时地对存储数据的桶数进行调整。与可扩展散列相比，线性散列不需要存放数据与可扩

30、展散列相比，线性散列不需要存放数据桶指针的专门目录项，且能更自然处理数据桶桶指针的专门目录项，且能更自然处理数据桶已满的情况已满的情况 但如果数据项键值散列后分布不均匀的偏斜度但如果数据项键值散列后分布不均匀的偏斜度大，导致的问题可能会比扩展散列还严重。大，导致的问题可能会比扩展散列还严重。2023年2月11日455.4.3 动态线性散列（动态线性散列（2）v动态线性散列技术概要动态线性散列技术概要v理解线性散列技术（参考书本理解线性散列技术（参考书本P63)v线性散列的技术特点线性散列的技术特点 每次桶分裂的触发条件允许灵活选择每次桶分裂的触发条件允许灵活选择 每次发生分裂的桶，总是由当前每

31、次发生分裂的桶，总是由当前Next值来决定，值来决定，与桶是否已满或溢出无关！与桶是否已满或溢出无关！为处理在已满桶中插入新数据项情况，需引入为处理在已满桶中插入新数据项情况，需引入溢出块。溢出块。由于在一轮中，每个初始桶总会轮到一次分裂，所由于在一轮中，每个初始桶总会轮到一次分裂，所以，一般情况下，桶的溢出块数不会超过以，一般情况下，桶的溢出块数不会超过1块。块。2023年2月11日465.4.3 动态线性散列（动态线性散列（4）2023年2月11日47v应用举例应用举例 例例5.7 假设：线性散列文件每个桶可存储线性散列文件每个桶可存储4个数据项，初始时有个数据项，初始时有4个桶，即个桶，

32、即N=4；初始时，初始时，Level=0，Next=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个二进制位。个二进制位。2023年2月

33、11日48例例5.7（续）（续）2023年2月11日49例例5.7（续）（续）2023年2月11日505.5 位图索引位图索引5.5.1 位图索引的结构 5.5.2 位图索引的应用5.5.3 压缩位图 5.5.4 压缩位图的游程解码操作5.5.5 位图索引的维护u是一种主要针对多键查询设计的特殊类型索引，是一种主要针对多键查询设计的特殊类型索引，尽管每个位图索引都是建立在单键码之上。尽管每个位图索引都是建立在单键码之上。u为了使用位图索引，关系或数据文件中的记录为了使用位图索引，关系或数据文件中的记录 必须进行顺序编号必须进行顺序编号1,2,n，使得给定一个编号，使得给定一个编号 i，能方便检

34、索到第，能方便检索到第i个数据记录。个数据记录。2023年2月11日51v考虑一个共有n个记录的关系R和它的一个属性A，假设R的所有记录在A上只有m个的不同取值，v 1,v2,vm。vR在A上的位图索引 是一组位图向量；是一组位图向量；R.A的每个取值的每个取值v j(j=1.m)，分别对应一个位图向量，分别对应一个位图向量bit_ vj；共有共有m个这样的位图向量。个这样的位图向量。bit_ vj是一宽度为是一宽度为n的二进制数，该数的第的二进制数，该数的第i位值位值 bit_vj i=1，如果第，如果第i条记录的条记录的R.A取值取值 vj;bit_vj i=0，如果第，如果第i条记录的条

35、记录的R.A取值取值 vj;5.5.1 位图索引的结构位图索引的结构2023年2月11日52位图索引示例位图索引示例（图（图5.11)2023年2月11日53v 例例5.10（续例（续例5.9，多键码检索应用示例），多键码检索应用示例）1.条件匹配查询条件匹配查询 gender=f income-level=L2(r)2.范围查询范围查询 gender=f income-levelL2(r)5.5.2 位图索引的应用位图索引的应用2023年2月11日54v 位图压缩的必要性位图压缩的必要性 当用于建立位图索引的属性不同值数很多时，位图索当用于建立位图索引的属性不同值数很多时，位图索引也可能会很

36、大。引也可能会很大。v 位图压缩技术的基本思想位图压缩技术的基本思想 对任何二进制数，我们总可以用对任何二进制数，我们总可以用i1个个0、i2个个0、i3个个0、来描述。由这个描述我们完全可以准确重构出来描述。由这个描述我们完全可以准确重构出这个二进制数。这个二进制数。但若直接对但若直接对i1,i2,进行二进制编码，就会出现问题。进行二进制编码，就会出现问题。比如，对长度为比如，对长度为3和和1的两个字段，合成为的两个字段，合成为111。无法唯一解码。无法唯一解码还原位图向量。还原位图向量。解决这个问题的一个有效方案：解决这个问题的一个有效方案：在数值在数值i的二进制编码前，加上一个前缀码。的

37、二进制编码前，加上一个前缀码。前缀码长度与值前缀码长度与值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 压缩位图压缩位图v例例5.11 对位图对位图0001000,0000110000,0000,0001进行编码；进行编码；解压缩码解压缩码11101101001011v位图压缩的效率分析：位图压缩的效率分析：

38、一个长度为一个长度为i的码长为的码长为2 log2i，上限为，上限为2 log2n 因为最大向量个数因为最大向量个数m4时，恒有时，恒有2 nlog2n n2 成立，且成立，且n越大压缩效果越大压缩效果越好。越好。2023年2月11日555.5.4 压缩位图的游程解码操作压缩位图的游程解码操作v当要对两个压缩的位图向量运算时，必须先解码后运算。但不必先执行全部解码，可以结合运算的进行，一次一个段，即一次一个游程地交替解码。v例5.12 对两个压缩位图向量对两个压缩位图向量A:00110110(字段序列字段序列0,5)和和B:11011111101101(字段序列为字段序列为7,13)进行与进行

39、与运算，结果向量为运算，结果向量为C。2023年2月11日565.5.4 位图索引的维护位图索引的维护v删除记录i 不调整位向量码长，仅将所有位图向量的第不调整位向量码长，仅将所有位图向量的第i位置为位置为0；同时将数据文件中对应的空间做删除标记；同时将数据文件中对应的空间做删除标记；v插入新记录 所有位向量在原来基础上补加所有位向量在原来基础上补加1个个0(对压缩码其实可不加对压缩码其实可不加)。根据新记录的索引字段值，进行如下调整：根据新记录的索引字段值，进行如下调整：若是新出现的索引字段值，则增加若是新出现的索引字段值，则增加1个位向量，并个位向量，并将该位向量的最后位改为将该位向量的最

40、后位改为1。若是已有的索引字段值值，则找到该值的位向量，若是已有的索引字段值值，则找到该值的位向量，将该位向量的最后位将该位向量的最后位(新加位新加位)置为置为1。v位图索引属性值被修改位图索引属性值被修改2023年2月11日575.6 多维索引多维索引5.6.1 多维空间索引技术综述 5.6.2 网格文件5.6.3 R树 5.6.4 k-d树与四叉树2023年2月11日585.6.1 多维空间索引技术综述多维空间索引技术综述4.已建议的空间索引结构综述已建议的空间索引结构综述3.需要多维空间索引的应用简介需要多维空间索引的应用简介点数据点数据(point data)与区域数据与区域数据(re

41、gion data)2.空间数据及其查询的主要类型空间数据及其查询的主要类型1.为什么需要多维空间索引为什么需要多维空间索引2023年2月11日595.6.1.1 为什么需要多维空间索引（为什么需要多维空间索引（1）v 例例5.13 设有一个存放购买金首饰顾客信息记录的关系表Customers(age,salary)，假定在age和salary上分别建有B+索引。现考虑age30 salary2K条件查询。v 处理这个查询的几种可选策略：处理这个查询的几种可选策略：1）先基于Customers:age上的B+索引找出所有age30的记录；再检查这些记录，进一步挑选出salary2K的记录。2）

42、先基于Customers:salary上的B+索引找出所有salary2K的记录；再检查这些记录，选出age30的记录。3）先根据两个B+索引，分别找出满足age30和salary 2K的记录指针；然后，在内存中求这两组指针交集，并由交集指针找出所有目标记录。利用位图索引可加快这种方法的交集操作。基于组合键建立B+树索引（仍是一维的）2023年2月11日605.6.1.1 为什么需要多维空间索引（为什么需要多维空间索引（2）v与与B+树相比，多维或空间索引则往往利用某种树相比，多维或空间索引则往往利用某种空间关系（在空间中的相近性或邻近性）来组织空间关系（在空间中的相近性或邻近性）来组织数据项

43、，如图数据项，如图5.12（b）所示。）所示。2023年2月11日615.6.1.2 空间数据及其查询的主要类型空间数据及其查询的主要类型（一）空间数据的主要类型（一）空间数据的主要类型（1）空间点数据）空间点数据 基本特点基本特点 只有位置，没有大小、边界，不占空间。只有位置，没有大小、边界，不占空间。常见点数据类型常见点数据类型 光栅数据光栅数据(raster data。多维特征向量多维特征向量(feature vector。（2）区域数据）区域数据 同时具有位置和边界的空间延展。同时具有位置和边界的空间延展。存储在存储在DB中的区域数据，通常是一些用来逼中的区域数据，通常是一些用来逼近实

44、际对象形体的系列简单几何体。近实际对象形体的系列简单几何体。2023年2月11日62空间查询空间查询(spatial queries)的主要类型的主要类型v 范围查询范围查询(range queries)空间范围查询通常关联着一个区域，并要求返回与目空间范围查询通常关联着一个区域，并要求返回与目标区域范围重叠标区域范围重叠(overlap)或位于目标区域内的、指定或位于目标区域内的、指定类型的所有区域对象。类型的所有区域对象。v 最邻近点查询最邻近点查询(nearest-neighbor queries)要求找出离指定点最近的某些对象。例如，查询要求找出离指定点最近的某些对象。例如，查询“找找

45、距某位置最近的距某位置最近的10个城市个城市”。在多媒体数据处理中，这种查询显得特别重要。在多媒体数据处理中，这种查询显得特别重要。v 空间连接查询空间连接查询(spatial join queries)典型例子包括典型例子包括“找相互间距离不超过找相互间距离不超过200公里的城市组公里的城市组对对”，“找靠近某区域（如一个湖泊）的所有城市找靠近某区域（如一个湖泊）的所有城市”v 部分部分(维维)查询查询 只指定部分维的值，查找匹配这些维值的所有对象；只指定部分维的值，查找匹配这些维值的所有对象；2023年2月11日63基于范围查询的最邻近点查询实现算法基于范围查询的最邻近点查询实现算法 20

46、23年2月11日645.6.1.3 需要多维空间索引的应用简介需要多维空间索引的应用简介数据仓库的数据立方体地理信息系统(GIS)CAD/CAM系统多媒体信息处理2023年2月11日65v 在数据仓库中在数据仓库中,通常需要建立一种称为通常需要建立一种称为“数据立方体数据立方体”的多维数据结构的多维数据结构,以更好支持决策分析。以更好支持决策分析。v 例如，一个全国性连锁店，可能记录每一笔销售，包例如，一个全国性连锁店，可能记录每一笔销售，包括销售时间、销售地区和商品的种类等。括销售时间、销售地区和商品的种类等。事实数据事实数据事实表；事实表；可能影响这些销售事实数据的可能影响这些销售事实数据

47、的各因子，如时间、地区和商品类型等属性，作为不各因子，如时间、地区和商品类型等属性，作为不同的观察维度同的观察维度维表维表。将所有维属性区段组合想象为一个个将所有维属性区段组合想象为一个个多维盒式单元多维盒式单元，每个事实量（如销售量、销售额等）想象为存储在每个事实量（如销售量、销售额等）想象为存储在这些多维盒单元中的一个量。这些多维盒单元中的一个量。本质上，可将事实表中每个元组视该空间的一个点。本质上，可将事实表中每个元组视该空间的一个点。分析人员可按某些维对数据进行分组，并通过聚合分析人员可按某些维对数据进行分组，并通过聚合操作对这些分组进行汇总操作对这些分组进行汇总。5.6.1.3 数据

48、仓库的数据立方体数据仓库的数据立方体图图5.142023年2月11日66vGIS被广泛用来处理各种空间数据，包括点、线、被广泛用来处理各种空间数据，包括点、线、二维二维/三维三维-区域。区域。例如，一幅地图中，可能同时包含小目标例如，一幅地图中，可能同时包含小目标（点）、河流（点）、河流/公路（线），以及城市公路（线），以及城市/湖泊（区湖泊（区域）等。域）等。vGIS能自然提出所有空间查询类型，它必须能有能自然提出所有空间查询类型，它必须能有效管理二维、三维数据集效管理二维、三维数据集,必须能有效处理空间必须能有效处理空间点数据和区域数据。点数据和区域数据。v当前许多对象数据库系统的都已能很

49、好支持常见当前许多对象数据库系统的都已能很好支持常见的的GIS类应用。类应用。5.6.1.3 地理信息系统地理信息系统(GIS)2023年2月11日675.6.1.3 CAD/CAM系统系统 v这类系统中通常要存储和处理大量的空间对象。这类系统中通常要存储和处理大量的空间对象。类似类似GIS，这类系统中也必须存储和处理空间点，这类系统中也必须存储和处理空间点/区域数据。区域数据。v范围查询和空间连接查询可能是这类应用中最常范围查询和空间连接查询可能是这类应用中最常见的查询。见的查询。vCAM/CAD也是对象数据库系统发展的一个主要也是对象数据库系统发展的一个主要动因。动因。2023年2月11日

50、68v多媒体涵盖诸如图像、文本和各种类型时间序列多媒体涵盖诸如图像、文本和各种类型时间序列数据（音频数据（音频/视频）等各类对象，也需要空间管视频）等各类对象，也需要空间管理方式。理方式。v在多媒体数据库在多媒体数据库(multimedia databases)中，中，使用象使用象“查找与特定对象相似的所有对象查找与特定对象相似的所有对象”这类这类相似查询可能极为普遍。相似查询可能极为普遍。v回答相似查询的一个通行方法是首先映射回答相似查询的一个通行方法是首先映射/变换变换多媒体对象到特征向量点，将查找相似对象问题多媒体对象到特征向量点，将查找相似对象问题转换为关于特征向量点集的最小邻近点查询

51、问题。转换为关于特征向量点集的最小邻近点查询问题。5.6.1.3 多媒体信息处理多媒体信息处理2023年2月11日69基于内容的图像检索技术基于内容的图像检索技术v医疗/生物图像数据库 可能要存储大量数字化的二维可能要存储大量数字化的二维/三维图像，如三维图像，如X-射线或射线或MRI图像，形成相对完整的、涵盖各种案例的样本图图像，形成相对完整的、涵盖各种案例的样本图像库；像库；可基于图像相似匹配技术，处理新采集图像的模式识可基于图像相似匹配技术，处理新采集图像的模式识别问题。别问题。v基于指纹数据库，进行给定指纹的匹配搜索，处理指纹识别问题。v基于人脸图像数据库，进行给定人脸的匹配搜索。v视

52、频剪辑数据库。在视频DB中，搜索有场景变化的特别帧，或搜索包含特别对象的视频帧序列，来跟踪处理运动对象。v存储文本文档集，并处理“在文档集中搜索包含相似主题文档”等有关问题。以上应用以上应用,本质上都要处理相似图像的匹配本质上都要处理相似图像的匹配/识别问题。识别问题。2023年2月11日705.6.1.4 已建议的空间索引结构综述已建议的空间索引结构综述 v建议了许多空间索引结构。建议了许多空间索引结构。有些索引结构主要是为满足空间数据点检索需有些索引结构主要是为满足空间数据点检索需要而设计的；要而设计的；以处理点数据为主的索引结构包括网格文件、以处理点数据为主的索引结构包括网格文件、hB树

53、、树、kd树、点四叉树树、点四叉树(point quad trees)和和SR树。树。也有些能自然处理区域数据。而能自然处理区也有些能自然处理区域数据。而能自然处理区域数据的索引结构则包括区域四叉树域数据的索引结构则包括区域四叉树(region quad trees)、R树和树和SKD树等。树等。2023年2月11日715.6.2 网格索引结构（网格索引结构（1）例例5.14 设有一个存放顾客购买金首饰记录的关设有一个存放顾客购买金首饰记录的关系表系表(age,salary)。为使问题简化，我们假设该。为使问题简化，我们假设该关系只有顾客年龄和月薪两个属性。关系只有顾客年龄和月薪两个属性。-实

54、例数据中有12个顾客，相关记录被表示成下列的年龄-薪水对：(26,0.6)(45,0.6)(51,0.75)(51,1)(51,1.28)(70,1.30)(85,1.4)(30,2.6)(26,4.0)(45,3.5)(51,2.75)(60,2.6)2023年2月11日725.6.2 网格索引结构（网格索引结构（2）2023年2月11日735.6.2 网格索引结构（网格索引结构（3）v网格数组的每个单元网格数组的每个单元(Cell)含有一个指向桶的指含有一个指向桶的指针，每个桶可以是一个页或页组，桶中直接存放针，每个桶可以是一个页或页组，桶中直接存放记录。为了节省空间，网格的多个单元可以指

55、向记录。为了节省空间，网格的多个单元可以指向同一个桶。同一个桶。v网格文件的插入算法网格文件的插入算法 举例：在图5.16网格中，插入记录(70,3.5K)。有关步骤请参见书本 P177-178 v网格文件对多维查询支持及性能网格文件对多维查询支持及性能 对指定点的查找，若无溢出块页，仅需对指定点的查找，若无溢出块页，仅需1次次I/O；部分匹配：可能需要查找桶矩阵的某行或某列部分匹配：可能需要查找桶矩阵的某行或某列的所有桶，的所有桶，I/O数可能很大；数可能很大；范围查询：检查与范围区域有相交的所有桶；范围查询：检查与范围区域有相交的所有桶；2023年2月11日74vR-树也是一种平衡树结构，

56、其中被索引的多边形树也是一种平衡树结构，其中被索引的多边形存储在叶节点上存储在叶节点上(这一点很象这一点很象B+树树)。v每个树节点每个树节点(叶节点叶节点/内节点内节点)都对应有一个平行都对应有一个平行于坐标轴的矩形边界框。于坐标轴的矩形边界框。v叶节点叶节点 负责存储位于其内的所有被索引多边形，边界负责存储位于其内的所有被索引多边形，边界框是一个能涵盖其内所有存储对象的最小矩形。框是一个能涵盖其内所有存储对象的最小矩形。v内节点内节点 存储其每个子节点的边界框和指向各子节点的存储其每个子节点的边界框和指向各子节点的指针。指针。vR树的基本操作：查找、删除和插入5.6.3 R树树2023年2

57、月11日75R树的两种视图树的两种视图2023年2月11日76v 向向R树中插入一个多边形树中插入一个多边形(令其边框为令其边框为target_PB)我们我们需选择一个叶节点存放该多边形。需选择一个叶节点存放该多边形。理想的情况是，我们能找到一个叶节点：它仍有空的理想的情况是，我们能找到一个叶节点：它仍有空的项目空间，而且它的边界框包含该多边形的边界框。项目空间，而且它的边界框包含该多边形的边界框。也可能不存在这样节点；即使存在，找到它也是非常也可能不存在这样节点；即使存在，找到它也是非常昂贵，因为不可能从根向下一次遍历就找到它。昂贵，因为不可能从根向下一次遍历就找到它。在每个内部节点我们可能

58、发现多个子节点边界框包含在每个内部节点我们可能发现多个子节点边界框包含target_PB，而每个这样的子节点都要搜索。，而每个这样的子节点都要搜索。v 可借助一种启发式的算法，来完成可借助一种启发式的算法，来完成R树的插入任务。树的插入任务。5.6.3 R树树-插入算法插入算法2023年2月11日77v考虑一维数据点的索引：考虑一维数据点的索引：树结构树结构(如二叉树或如二叉树或B-树树)都是通过不断划分来都是通过不断划分来分割空间的。分割空间的。vk-d树树(k维搜索树维搜索树)是早期用来建立多维空间索引是早期用来建立多维空间索引的一种简单树形结构。的一种简单树形结构。每个节点将一个空间划分

59、为两个子空间。每个节点将一个空间划分为两个子空间。划分首先通过树顶层节点的一个维进行，然后划分首先通过树顶层节点的一个维进行，然后在紧接的下一个层节点上用另一个维进行划分，在紧接的下一个层节点上用另一个维进行划分，以此类推。以此类推。vk-d树数据结构特点（参见书本树数据结构特点（参见书本P181-182)5.6.4 KD树树2023年2月11日785.6.4 KD树树-示例示例2023年2月11日79v 部分匹配查询部分匹配查询 如果给定某属性的值，那么，当处在恰好是按该属性如果给定某属性的值，那么，当处在恰好是按该属性划分的层结点时，只需考察一个方向的子结点；否则划分的层结点时，只需考察一

60、个方向的子结点；否则要考察两个方向的子结点。要考察两个方向的子结点。v 范围查询范围查询 如范围跨越结点划分值时，需考察两个方向的子结点如范围跨越结点划分值时，需考察两个方向的子结点树。树。v 最邻近查询最邻近查询 可通过多次的范围查询来实现。可通过多次的范围查询来实现。v 主要存在问题主要存在问题 每结点占用每结点占用1个页个页,空间利用率低；空间利用率低；查询路径可能会很长；查询路径可能会很长；解决方案：解决方案：采用多分枝内结点采用多分枝内结点(但这已不是但这已不是k-d树了树了)；聚集多个内结点到一个页聚集多个内结点到一个页 5.6.4 KD树树-对多维查询支持对多维查询支持2023年

61、2月11日80v四叉树四叉树(quadtrees)是另一种组织二维空间数是另一种组织二维空间数据索引存储的方法。据索引存储的方法。v四叉树的每个节点关联到空间的一个矩形区四叉树的每个节点关联到空间的一个矩形区 顶层节点关联整个目标空间，顶层节点关联整个目标空间，每个节点有四个子节点关联到该节点所代表矩每个节点有四个子节点关联到该节点所代表矩形区的四个象限。形区的四个象限。叶节点有叶节点有0个或多个不超过最大数的数据项数。个或多个不超过最大数的数据项数。如果超过了指定的最大数据项数，叶节点转为如果超过了指定的最大数据项数，叶节点转为节点，并进行四等分象限划分。节点，并进行四等分象限划分。5.6.5 四叉树四叉树