最新四章空间数据库索引技术3ppt课件PPT课件 70页

'四章空间数据库索引技术3ppt课件 一、DBMS索引技术1.索引顺序存取方法2.多层索引树（1）B-树（2）B＋-树 （1）检索从根节点开始，进行关键字的比较。（2）插入如果在找到的插入位置叶子节点的元素个数不足2m个，直接插入。如果在插入的位置叶子节点已经有2m个，则进行分裂。 分裂过程：将数据按顺序插入，然后将该叶子结点对分，其中前半部分仍然存放原来结点中，后面的放在一个新申请的结点中，并将中间一个元素放在父结点中。如果父结点中的元素也已经满了，则父结点必须进行分裂。 插入27，分裂后，22加入到父结点中。 （3）删除x检索到后，如果在叶子节点上，则进行删除，如果不在叶子节点上，则要用一个比x大的元素y代替x。y即x右边指针所指路径最左边叶子节点的第一个元素。然后在叶子节点中删除y。 删除y后，如果叶子节点元素数量小于m，则与它相邻的左（右）结点借一个元素；如果兄弟结点元素数量正好为m，则进行叶子节点的合并。合并完成后，父结点少了一个子树，则也可能存在合并的问题。 3.B+树B树随机检索效率很高，但是遍历所有元素却不方便。这是因为，B树的非叶子节点同样存储数据。B+树是B树的变形，在非叶子节点中存放的不是数据。 定义：一个2m+1阶的B树满足，（1）每个结点至多有2m+1棵子树（2）除根节点外，其他每个分支至少有m+1棵子树。（3）非叶子节点的根节点至少有两个子树。（4）有n棵子树的非叶节点有n-1个关键码。（5）叶节点都在同一个层上，存放了数据文件中记录关键码以及指针。叶节点按照关键码值排序链接。（6）所有分支结点可看成是索引的索引。仅存放各子节点的最大（最小）关键码的分界值及指针。 B+树包含两部分：首先是B树索引。然后链接各叶子节点的顺序链。即包含两个指针。 在插入和删除的方式上，与B树不同。B+树在插入时，与B树类似，不同在于分裂时，不仅要把元素上升到父节点中，并且在叶子节点中也要保留。 插入8叶结点保留原来元素，但是中间节点分裂时不保留。 B+树删除时比较简单。只需要删除叶子节点上的数值，而中间节点不需要改变。但是，这中间存在合并的过程。 上为删除19，20后，下为进一步删除24后。 二、空间数据库索引传统的数据库索引技术包括了B树、B+树、二叉树、哈希索引等，都是针对一维属性数据的主关键字索引而设计的。空间数据库索引基于这些技术分别取得了发展。 基于哈希表的检索 空间索引大致分为四大类：1.基于二叉树的索引技术2.基于B树的索引技术3.基于哈希的格网技术4.空间目标排序法 1.基于二叉树的索引技术主要有Kd树、KDB树等。其中，典型的Kd树是一种二分索引树结构，主要用于索引多维数据点，但对于复杂的空间目标，如折线、多边形等必须采用近似方法和空间映射技术。为了能索引复杂的空间目标，Mkd树被提出；为了将Kd树存储到外存，将Kd树与B树结合，得到KDB树。所有的方法对于非点状空间目标的索引效率都很低。 2.基于B树的索引技术目前很多空间数据索引技术，都是B树发展来的。例如R树、R+树、R*树等。利用最小外包矩形表示空间目标。 3.基于哈希的格网技术基本思路是将索引空间划分为相等或不相等的一些小方格网，与每个格网相关连的空间目标则存在同一磁盘页，而格网的访问地址则可以直接通过求数组下标或某种算法得到。 4.空间目标排序法将多维空间映射为一维空间，包括了Z序、Hilbert排序等。 （一）Kd树1.定义Kd树的每个节点表示K维空间的一个点，并且树的每一层都根据这层的分辨器（Discriminator）作出分枝决策。Kd树的第i层的分辨器定义为：iMODk（根节点为0层，下面依次加1）。特征如下：（1）左子树的所有节点的d维数值，均小于根节点的d维数值。（2）右子树的所有节点的d维数值，均大于根节点的d维数值。（3）左右子树也分别为kd树。d为根节点的分辨器。四、二叉树检索 A点分辨器的值为0（x轴），左子树的所有结点的x值都比A的x值小；右子树反之。 分辨器的值是指对应空间中的哪一维。因此，k层之后就是新的循环。首先是从第一维分成两个部分；然后是第二维分成两个部分；再次是第三维分成两个部分，直至第k维。然后重新按照第一维… Kd树查询：需要按照分辨器的值进行比较。Kd树插入：与二叉树同。Kd树删除：与二叉树类似，但是，对于结点的d维数值，存在相同情况，这就需要处理。 图中H和I的横坐标相同。 （二）K-D-B树KD树与B树结合，解决分页策略。 （三）HB树hB树是一种有效的多维动态索引结构,其结点间搜索和增长过程模拟B树的处理方法,结点内采用k维树组织和进行高效搜索。结点分裂要求k维树分裂,于是抽取一个大小介于1/3～2/3间并尽可能平衡的k维子树,并以此子树表示一个新结点。因此hB树结点空间是有孔(holey)的k方体,即每个结点空间是被抽取若干个小k方体的k方体. (b)中结点W的k维树是从结点Z的k维树抽取的，如Z的k维树中的ext标识，它相当于(a)中粗线框内的矩形从整个大矩形中抽取.结点P是该hB树的根,其k维树表示下层hB结点W,Z的导向路径,意为满足x＜x1且y＜y1的记录应存于结点W,其它记录则存于结点Z。符合二叉树原理，左边小于右边（a）二维空间的一个划分（b）对应的hB树结构y4 hB树能很好地支持精确匹配搜索和范围搜索。进行精确匹配搜索,要经过自hB树根到一叶子的单一路径，访问的结点数是hB树的高度。在hB树结点内通过比较k维树结点值与搜索的相应属性值，最终确定唯一的下层hB树结点。范围搜索可能涉及hB树每层的多个结点。范围的标界是在若干个属性上取值的上下界。结点内搜索时将k维树结点的比较值与搜索范围的相应属性上下界进行比较，以决定转向k维树结点的左子树、右子树或两者。 尽管hB树对于大多数情况能取得较好效果,但它有两个问题:(1)空间利用率不理想;(2)可能出现多父结点,使hB树不再是严格的树结构。 五.四叉树检索点四叉树区域四叉树MX四叉树PR四叉树CIF四叉树 1.点四叉树以空间点为划分点，将索引空间分为两两不相交的的2k个子空间，依次与它的2k个孩子结点相对应，对于位于某一子空间的点，则分配给对应的子树。 点四叉树的构造过程：（1）输入空间点A，以A为根节点并进行划分空间。（2）输入空间点B，B落入A的NW象限，并且A的NW象限为空，则B直接放入A的NW象限孩子结点。同理，C是A的SW孩子结点。（3）输入D，由于D落入A的NW象限，但是NW不为空，所以继续往下查找，得到B的NE象限为空，因此，D作为B的NE孩子结点。（4）同理，空间点E、F，分别为A的SE、NE孩子节点。 缺点：（1）尽管点四叉树构造简单，但是删除一个节点时，该节点对应的所有子树节点必须重新插入四叉树中，效率很差。（2）对于精确匹配的点查找，效率很高，但是对于区域查找，查找路径有多条，效率较差。（3）树的动态性差，树的结构完全由点的插入顺序决定。树的平衡难以保证。 区域四叉树(Region-BasedQuadtree)是以区域目标为循环分解对象的四叉树,分解过程既可以按照区域边界,也可以按照区域内部对二维空间进行划分。如果区域四叉树中的结点覆盖的区域中所有数组元素的值都相同，则该结点是叶子结点。否则，该结点是内部结点，被进一步划分为四个等大小的子结点。主要有MX四叉树与PR四叉树。避免了点四叉树的动态性差、结构完全由点的插入顺序决定的功能缺点。2.区域四叉树 MX四叉树MX四叉树将每个空间点看成是区域四叉树中的一个黑象素，或当成一个方阵（SquareMatrix）中的非零元素，因此称为MX四叉树。利用叶子节点为黑节点或空闲点表示数据空间某一位置空间点的存在与否。树的构造过程即是对整个数据空间重复地进行2k次等分，直到每一空间点都位于某一象限的最左下角的过程。 MX四叉树特点：空间中每一个点都属于某一象限且位于该象限的最左下角，每一象限只与一个空间点相关联。尽管D同时是两个大小不等的象限的最左下角，但其应属于最下一级象限（即最后一次空间划分所产生的子象限）。这就决定了所有空间点均位于叶子节点。 缺点：插入（或删除）一个点可能导致树的深度增加（或减少）一层或多层，所有的叶子节点都必须重新定位。树的深度往往很大，这会影响查找效率。 PR（PointRegion）四叉树叶子节点或者为空，或者包含唯一数据点。PR四叉树 PR四叉树与MX四叉树的构造过程类似，不同的是，当分解到一个象限只包含一个点时，不需要继续分解使该点位于某一子象限的最左下角。另外，插入或删除一个点也不会影响到其他的分支，操作比较简单。 PR四叉树与MX四叉树的区别：（1）数据点位于象限内，不要求位于左下角。（2）叶子节点可能不在树的同一层次。（3）PR四叉树的叶子结点数及树的深度都小于MX四叉树，因此PR四叉树效率高。 CIF四叉树CIF四叉树是为了表示VLSI（VeryLargeScaleIntegration)应用中的小矩形而提出的。它可以用于索引空间矩形及其他形体。表示方式与区域四叉树类似，数据空间被递归的细分，直至产生的子象限不再包含任何矩形。在分解过程中，所有与任一划分线相交的矩形与该划分线对应的象限相关联。 0数据桶的容量设为3。 相交查询：从根节点开始，首先检查与之关联的所有矩形是否为查找结果；接下来检查象限空间与查询区域相交的孩子结点….直到叶子节点。插入矩形：首先检查根节点，如果与根节点的划分线相交，则插入到根节点对应的桶链表中；否则检查包含该矩形的子象限的孩子结点…；如果检查到某一没有孩子的象限，而且该矩形依旧没有插入到对应的位置，那么该象限必须再次细分直到为该矩形找到对应的子象限。删除矩形：找到矩形所在结点，从数据桶中删除。如果删完后桶为空，且该节点没有孩子结点，则可以删除该节点。 CIF四叉树可以用于索引矩形以及任何其他形体的空间目标而不需要经过目标近似与空间目标映射，因此对于区与查询，效率相对MX、PR四叉树要高些。但是区域查询往往需要访问多个节点对应的存储桶，尤其当索引量增大，大区域节点所包含较多数据矩形时，外存I/O开销很大。 四叉树索引优点：结构清晰，容易建立。它同时具有聚集空间目标的能力（在栅格数据存储中发挥突出作用），提高了检索效率，得到广泛应用。有很多改进的方法被提出：（1）一体化索引，进行了索引空间的三级划分，包括索引块、基本格网、细分格网，并采用行次序法对各级区域进行了编码。（2）CELLQTREE，叶子节点索引点对象，中间节点索引线和面对象，较好的解决了大区域对象的标示符在子空间结点中的多次重复存储问题。 四叉树索引的缺点：当索引数据量较大时，如果四叉树层次过小，将导致查找性能下降；如果四叉树层次过大，将导致重复存储的增加，从而增加空间开销，这同时又会影响查找性能。 六、基于B-树的空间索引（一）R-树R-树是B-树在多维空间的扩展，由Guttman提出。其特点是能索引一定范围内的对象。其叶子节点包含多个形式为(OI，MBR)的实体,OI为空间目标标志,MBR为该目标在k维空间中的最小包围矩形。非叶子节点包含多个形式为(CP，MBR)的实体。CP为指向子树根节点的指针，MBR为包围其子节点中所有MBR的最小包围矩形。 R树的定义：设M为节点中包含子节点的最大个数，m（2≤m≤M/2)为节点包含索引项（数据项）的最小数目。（1）根节点不是叶子节点，则至少有两棵子树。（2）除根之外的所有中间节点至多有M棵子树，至少有m棵子树。（3）每个叶子节点均包含m至M个数据项（4）所有的叶子节点都出现在同一层次上（5）所有节点需要同样的存储空间。特性：数据矩形可能重叠；目录矩形允许重叠；查找路径多条。 R树的特点决定了，为了高效，需要：（1）目录矩形“面积”尽可能小，“死空间”尽可能小（即目录矩形内的空白区域）。（2）目录矩形间重叠尽可能小，可以减少查找路径。（3）目录矩形“周长”尽可能小。这可以尽量让目录矩形为“方”形，从而改善树的结构，减少目录矩形面积。（4）空间利用率尽可能高。但实际上这四条互相影响，很难提高。 查找：（查找与红框P相交区域）（1）从根节点开始，比较个目录矩形是否与P相交，因此R1、R2都与P相交。需要比较R1、R2所包含的子树。（2）R1中的目录矩形，只有R5与P相交。进一步比较R5所对应的目标矩形，得到r7、p7。p7确定相交，r7需要根据其空间坐标进一步判断。（3）同理得出r8要进一步判断。 插入：（只是按照“最小覆盖面积”的原则）从根节点开始，寻找下一个节点，遵循：（1）包围新增目标后，目录矩形的“面积”增量最小（2）如果增量相同，目录矩形面积最小。 分裂：原则上，分裂之后的覆盖面积尽可能小。这样在检索时可以减少检索的次数。错误的分裂正确的分裂 分裂的最直接方法是遍历，即对所有可能的组合进行计算，选择最优，但是代价太大，计算次数为2M-1次。通常M取值50，则计算次数为248，这是不可能的。变通的方法：平方级分裂算法：要求首先得到两个最浪费的对象，即这两个点构成的矩形，其面积减去这两个对象本身的面积后，差值最大。然后选择一个新对象，计算这个对象增加到两个矩形之后的面积增量d1,d2，要求|d1-d2|最大。把这个对象添加到面积增加小的矩形中去。不能保证找到最优解。计算代价与M平方相关，与空间维数线性相关。 删除：从R树中删除一个目标，首先需要找到存放该目标的叶节点，再删除该目标对应数据项，并向上依次调整父节点对应索引项的目录矩形直至根节点。如果删除该目标对应数据项后叶节点下溢，则重新插入该叶节点中剩余的所有数据项于树的叶节点层，然后释放此叶节点的存储空间，最后删除其父节点中与该叶节点对应的索引项。例，删除r1，路径为：根节点->R1->R3，找到r1的叶节点并删除之，然后调整R3目录矩形使之完全包围p1、p4，调整R1的目录矩形，使之完全包围R3、R4、R5。 结束语谢谢大家聆听！！！70'