数据库第三章

数据库第三章第一页，共四十三页，编辑于2023年，星期三关系account(branch-name,loan-number,balance)，在branch-name和balance属性上分别都有索引。考虑针对该关系的一个多维查询：

SELECTloan-numberFROMaccountWHEREbranch-name=’Perryridge’andbalance=1000第二页，共四十三页，编辑于2023年，星期三有三种策略可处理这个查询：用基于branch-name的索引来找出所有branch-name=’Perryridge’的记录。然后，再检查这些记录，进一步挑选出balance=1000的记录。用基于balance的索引来找出所有balance=1000的记录。然后，再检查这些记录，进一步挑选出branch-name=’Perryridge’的记录。先根据两个索引，分别找出满足branch-name=’Perryridge’和balance=1000的记录指针，然后，在内存中求这两组指针交集，再通过属于交集中的指针找出所有目标记录。利用位图索引可以加快这种方法的交集操作。第三页，共四十三页，编辑于2023年，星期三5.1需要多维索引的应用简介5.1.1数据仓库的数据立方体在数据仓库中，通常需要建立一种称为“数据立方体”的多维数据结构，以更好支持决策分析。例如，一个全国连锁店，可能记录每一笔销售，包括销售时间、销售地区和商品的种类等。可以把销售量、销售金额等数据作为希望观察的事实数据，而把可能影响这些销售事实数据的各因子，如时间、地区和商品类型等属性，作为不同的观察维度。每个元组是该空间的一个点。然后，分析人员可按某些维对数据进行分组，并通过聚集汇总这些分组。第四页，共四十三页，编辑于2023年，星期三第五页，共四十三页，编辑于2023年，星期三设销售事实表为Sales(dt_id,area_id,product_id,sales_count)它通过dt_id、area_id、product_id三个属性分别关联到时间维表dt_dim、地区维表area_dim和产品维表prod_dim。我们可通过发出如下的SQL语句，来获得与示图等效的数据立方体。SELECTdt_dim.season,area_dim.city,prod_dtype,sum(sales_count)FROMsalesINNERJOINdt_dimONsales.dt_id=dt_dim.dt_idINNERJOINarea_dimONsales.area_id=area_dim.area_idINNERJOINprod_dimONd_id=prod_d_idWHEREdt_dim.year=2009GROUPBYdt_dim.serson,area_dim.city,prod_dtype第六页，共四十三页，编辑于2023年，星期三5.1.2空间数据与地理信息系统有两种类型的空间数据特别重要。计算机辅助设计(CAD)数据：包括如何构造物体的一些空间信息、集成电路设计信息等。地理数据：例如道路地图、行政区域地图。地理信息系统(GIS)是适用于存储地理数据的专用数据库系统.许多数据库系统都添加了对地理数据的支持，如IBMDB2SpatialExtender,InformixSpatialDatablade和OracleSpatial。第七页，共四十三页，编辑于2023年，星期三地理数据库的用途地理数据库有多种用途，包括联机地图服务、交通导航系统、公共服务设施分布网络信息等。当前，基于Web的道路地图及相关设施服务，已成为广受人们青睐的WEB应用程序。交通导航系统是装载在车辆上的、提供道路地图和旅行计划服务的移动地理信息系统。GPS是移动GIS的一个有效附件，能利用GPS卫星，以几十米的精度确定当前位置。第八页，共四十三页，编辑于2023年，星期三几何信息表示方法在DB中，各种几何结构有很多规范化的表示形式。可采用顺序列出多边形顶点来表示多边形，也可用三角形剖分多边形的方法表示多边形。复杂多边形被赋予一个标识符。第九页，共四十三页，编辑于2023年，星期三地理数据地理数据实际上就是空间数据。地图和卫星图像就是典型的例子。地图不仅可以提供位置信息，如边界、河流和道路等，而且还可提供很多与位置区域相关的信息，如海拔、年降水量等。第十页，共四十三页，编辑于2023年，星期三地理数据可分为两类：矢量数据(vectordata)由基本几何对象构成，如点、线段、三角形和二维多边形，以及圆柱体、球体、立方体和其它多维几何体。光栅数据(rasterdata)。这种数据由二维或更高维的位图或象素图组成。二维光栅图的典型例子是卫星云图，其中每个象素存储了特定地区的云层可见度。这种数据也可以是三维的，例如，同样在卫星的帮助下测得的不同地区在不同高度下的温度分布。时间可以形成另一个维度。设计数据库通常不存储光栅本身数据。第十一页，共四十三页，编辑于2023年，星期三相应地理数据表示也有两种：地理特征可表示成复杂多边形。某些特征（如河流）可以表示成复杂曲线或复杂多边形。我们可用多边形表示区域，每个多边形表示一个区域，区域内部的数组值是相同的。关于地区的地理信息（如年降水量），可以表示成一个数组，也就是光栅的形式。第十二页，共四十三页，编辑于2023年，星期三空间查询的三种主要类型临近查询：要求找出指定位置的对象。最近邻查询(nearest-neighborquery)则要求找出离指定点最近的对象。部分查询：只指定部分维的值，查找维上匹配这些值的所有点或形状；区域查询：查找全部或部分位于指定区域内的对象。查询还可能要计算区域的交和并。例如，查询年降水量低和人口密度高的区域。计算区域交的查询可被看作计算空间连接。

第十三页，共四十三页，编辑于2023年，星期三5.2空间数据索引结构5.2.1用传统索引执行范围查询可采用的处理方案：为每一维(x和y)各建立一个辅助索引(不妨设索引结构是B树)；通过x的B树索引，找出x在范围内的所有指针；通过y的B树索引，找出y在范围内的所有指针；如主存能存放下x,y在查询范围内的所有指针，可直接在主存中求指针交集。执行查询所需的I/O数估算公式：

B-树查找的少量I/O＋B-树需被检查的叶结点数＋读数据记录块的I/O数

第十四页，共四十三页，编辑于2023年，星期三示例问题考虑一个含100万个记录点的关系(x,y)，随机分布在(0,0)－(1000,1000)矩形区域内。设：每个块可存放100个记录点的数据，B-树的1个叶结点约有200个键值－指针对；x值落在[450,550]范围内的记录点数约有10万个，y也是如此，而x和y同时落在[450,550]范围内的记录点数约有1万个。试估算执行范围450≤x,y≤550内的记录点查询所需的I/O次数。第十五页，共四十三页，编辑于2023年，星期三I/O数估算每块可存放100记录点，100万记录点，共需1万个块存储数据。每个叶节点可存200记录指针，x落在[450,550]内约有10万记录个点，共需500个叶节点。如果B-树根节点驻留主存，则我们检索关于x的B-树，找出x在[450,550]内的所有指针，需要501次的I/O同样，找出y在[450,550]内的所有指针，也需501次I/O。合计1002次I/O。最后对已找到的1万个交集指针，还需进行实际记录数据的读取。由于记录随机存放，可能需要检索包含1万个记录点的所有块。第十六页，共四十三页，编辑于2023年，星期三5.2.2网格索引结构本章后面介绍常使用的一个例子：有一个存放顾客购买金首饰记录的关系表(age,salary,…)表中有12个顾客，他们的记录表示成下列的年龄-薪水对：

(26,0.6)(45,0.60)(51,0.75)(51,1.0)(51,1.28)(70,1.30)(85,1.4)(30,2.60)(26,4.0)(45,3.5)(51,2.75)(60,2.6)

第十七页，共四十三页，编辑于2023年，星期三基于年龄和月薪这两搜索键建立的网格索引结构第十八页，共四十三页，编辑于2023年，星期三一个网格文件有一个网格数组(gridarray)和两个与搜索键对应的线性标度(linearscale)。网格数组的每个单元(Cell)含有一个指向桶的指针，每个桶可以是一个块或物理相邻的块组，桶中直接存放记录。为了节省空间，网格数组的多个单元可以指向同一个桶。第十九页，共四十三页，编辑于2023年，星期三插入一个搜索键为(70,3.5K)的记录：

首先，我们用顾客月薪的线性标度，来定位新Cell的行，按顺序它应位于第3行。如果搜索键≥所有现有标度元素，则取最后一行。其次，我们用顾客年龄的线性标度定位新Cell的列。本例中，应定位到第3列。存储包含搜索键值(70,3.5K)的记录到桶j中。第二十页，共四十三页，编辑于2023年，星期三必须选择线性标度，使得记录能尽可能均匀分布在各Cell上。当需要往一个已经满的桶中插入记录时，系统必须为该桶添加挂接溢出块。但如果一个桶挂接的溢出块过多，会影响系统的性能。为改善这种情况的性能，如果指向有溢出块桶(令为A)的Cell数超过1，可先分裂A桶，即增加1个桶(令为B)，并调原先指向A桶的部分Cell指针，使其指向B桶。如果指向有溢出块桶的Cell数只有1个，这是，我们只有重新组织网格文件，扩展网格数组和扩展某个搜索键的线性标度，这一过程很类似可扩展散列中扩展桶地址表。第二十一页，共四十三页，编辑于2023年，星期三网格文件对多维查询支持：对指定点的查找，若无溢出块，仅需1次I/O；部分匹配：可能需要查找桶矩阵的某行或某列的所有桶，I/O数可能很大；范围查询：检查与范围区域有相交的所有桶；第二十二页，共四十三页，编辑于2023年，星期三要回答简单范围查询：Age>20andsalary<1K

满足这个条件的所有单元第0行的1～4列上。找出这些单元所指向的桶(本查询，有两个桶)，并有在桶中查找相应的记录。由于桶中可能包含其它一些不满足查询条件的记录，因此，需要对桶中记录的搜索键进行逐个检查。但为了回答这个查询，我们只需要检查很少的几个桶。第二十三页，共四十三页，编辑于2023年，星期三网格文件存在主要问题概念上，将二维网格扩展到n维网格数组，也是很简单的；但实际很少使用。对于多键查询，网格文件有效减少查询处理时间。然而，它也带来了：额外的空间负荷(存放含桶指针的网格数组、各搜索键的线性标度信息）；额外的性能负荷(进行记录插入和删除时)。此外，为搜索键选择合适的标度划分，使得记录能尽可能均匀分布，也往往是很困难的一件事。若插入到网格很频繁，还必须定期执行重新组织，这往往也需要付出很高的代价的。第二十四页，共四十三页，编辑于2023年，星期三5.2.3K-d树(k维搜索树)

早期建立多维空间索引的一种简单树形结构。每个节点将一个空间划分为两个子空间。划分首先通过树顶层节点的一个维进行，然后在紧接的下一个层节点上用另一个维进行划分，以此类推。

K-d树的数据结构特点

是二叉树的变种或推广；每个内结点关联1个属性及其属性值，将数据记录点在该属性维上划分为两部分；不同层结点关联不同属性；所有属性在层间循环；叶结点是存储块，存储尽可能多的记录。第二十五页，共四十三页，编辑于2023年，星期三k-d树及其所隐含的空间划分第二十六页，共四十三页，编辑于2023年，星期三k-d树的性能及对多维查询支持部分匹配查询当给定某些属性值，属性在属性值已知的层的结点上时，只需考察一个方向的子结点；当处于属性值未知的结点上时，必须考察它的两个方向的子结点；例：年龄为51的所有点范围查询有时一个范围允许移动到结点的唯一的一个子结点如范围跨越结点划分值时，需考察两个方向的子结点树例：年龄35-55薪水1K-2K最邻近查询可通过多次的范围查询实现；第二十七页，共四十三页，编辑于2023年，星期三k-d树应用的主要问题每结点占用1个块,空间利用率低；查询路径可能会很长；解决方案聚集多个内结点到一个块。第二十八页，共四十三页，编辑于2023年，星期三5.2.4四叉树(quadtrees)四叉树的每个节点关联到空间的一个矩形区。顶层节点关联整个目标空间。每个节点有四个子节点关联到节点所代表矩形区的四个象限。叶节点有0个或多个不超过最大数的数据点数。如果超过了指定的最大数据点数，叶节点转为节点，并进行四等分的象限划分。第二十九页，共四十三页，编辑于2023年，星期三5.2.4四叉树(quadtrees)在一个四叉树中，每个结点对应于二维空间中的一个矩形区域如果一个矩形中的点数不比一个块中能存放的数多，则这个矩形看作树的叶结点如果矩形中有太多点一个块存放不下，把它看作内部结点，它的子结点对应它的四个象限对于象限和结点的子结点使用指南针标示法

ⅡNW西北ⅢNE东北ⅠSW西南ⅣSE东南第三十页，共四十三页，编辑于2023年，星期三四叉树及其所隐含的空间划分50,2.5K75,1.2525,3.7545,0.6k50,2.75k60,2.6k50,1.0k50,1.28k50,0.75k30,2.6k25,4.0k45,3.5k0204060801005K************4K3K2K1K0K四叉树四叉树所隐含的空间划分26,0.6kIIIIVIIIⅡIV70,1.3k85,1.4kIIⅠIVⅢ第三十一页，共四十三页，编辑于2023年，星期三5.2.5R树GUTTMAN在1984年提出了R树索引。R树索引是最早支持扩展对象存取方法之一，R树是一个高度平衡树，它是B树在k维上的自然扩展。R树中用最小外包矩形(MBR)来表示对象范围，它开辟了空间索引研究的新方向。第三十二页，共四十三页，编辑于2023年，星期三5.2.5R树SELLIS(1987)，GREENE(1989)，BECKMANN(1990)，KAMEL(1994)和GARCFA(1998)等人在其基础上不断地进行改进，提出了R树的多种变形，形成了由R树、R+树、R*树、HilbertR树、SR树等组成的R树系列空间索引。R树及其众多变形都是一种平衡树，结构非常类似于B树，也具有类似于B树的一些性质，从而形成了一个R树索引体系。R树是一种利用B树的某些本质特征来处理多维数据的数据结构。R树表示由二维或更高维区域组成的数据，称之为数据区。一个R树的内结点对应于某个内部区域，原则上，区域可以是任何形状。第三十三页，共四十三页，编辑于2023年，星期三

5.2.5

.1R-树的定义M是一个节点中记录数目的最大值,常令2≤m≤M/2为一参数,说明一个节点记录的最小值,m可作为调节树结构的一个可变参数对于一棵M阶的R树，其结点结构可描述如下：(1)叶子结点：(COUNT，LEVEL，<OI1，MBR1>，<OI2，MBR2>，…，<OIM，MBRM>)(2)中间结点：(COUNT，LEVEL，<CP1，MBR1>，<CP2，MBR2>，…，<CPM，MBRM>)<OIi,MBRi>称为数据项，OIi为空间目标的标识，MBRi为该目标在k维空间中的最小约束矩形(简称为数据矩形)；<CPi,MBRi>称为索引项，CPi为指向子树根结点的指针，MBRi代表其子树索引空间，为包围其子树根结点中所有目录矩形或数据矩形的最小约束矩形(简称目录矩形)。m≤COUNT≤M指示结点中用到的索引项或数据项个数(即结点的“孩子”个数);LEVEL>0指示结点在树中的层数。由于整数和指针所占存储空间相同，且可以相互转换，因此R树的叶子结点和中间结点在结构上是相同的。第三十四页，共四十三页，编辑于2023年，星期三5.2.5

.1R-树的定义设m(2≤m≤M/2)为结点包含索引项(数据项)的最小数目(m通常取M/2，如果结点包含数目项小于m，则称结点下溢，如果结点包含项目数大于M，则称结点上溢或溢出)。R树必须满足如下特性：1．若根结点不是叶子结点，则至少有两棵子树；2．除根之外的所有中间结点至多有M棵子树，至少有m棵子树；3．每个叶子结点均包含m至M个数据项；4．所有的叶子结点都出现在同一层次；5．所有结点都需要同样的存储空间(通常为一个磁盘页)。第三十五页，共四十三页，编辑于2023年，星期三

R树的基本结构

R-树也是一种平衡树结构，其中被索引的多边形存储在叶节点上(这一点很象B+树)。每个树节点(叶节点/内节点)都对应有一个平行于坐标轴的矩形边界框。叶节点负责存储位于其内的所有被索引多边形(对非矩形多边形，还允许可选地存放其边界框，以方便检索)，叶节点边界框是一个能涵盖其内所有存储对象的最小矩形。内节点存储其每个子节点的边界框和指向子节点的指针。

第三十六页，共四十三页，编辑于2023年，星期三一棵R树R树平面图R树结构图第三十七页，共四十三页，编辑于2023年，星期三一棵R树上图是一棵R-树的示意图，（1）图中的白色框表示空间对象的MBR，即数据矩形，（2）兰色框表示中间结点(包括根结点)索引项对应的索引空间，即目录矩形。从图中可以看出R-树还具有如下特性：（1）数据矩形可能重叠；（2）目录矩形允许重叠(即中间结点的索引空间允许重叠)；（3）即使对于精确匹配查找，查找路径也往往是多条的；（4）R树是完全动态的，插入、删除、查询可以交叉进行，不需定期的全局结构重组。第三十八页，共四十三页，编辑于2023年，星期三

R树的相关算法R-树的查询操作R-树的查找算法是一个递归过程。设搜索区S，则搜索区域S内空间对象的过程如下：1．子树的查找：从R树的根结点T开始，如果T