数据库索引
前言：想要写出一篇令人眼前一亮的文章吗？我们特意为您整理了5篇数据库索引范文，相信会为您的写作带来帮助，发现更多的写作思路和灵感。
数据库索引范文第1篇
中图分类号:TP311文献标识码:A 文章编号:1009-3044(2010)02-268-03
Research on Spationtemporal Database Indices
ZHOU Yong-gang
(Department of Computer Technology, Anhui Vocational College of Posts and Telecom,Hefei 230031,China)
Abstract: To efficiently store, query and update trajectories of moving objects in spatio-temporal database,indexing techniques are sticking points. This paper thoroughly analyzed indexing methods for Spatio-Temporal Database, and finally some open researching problems and interesting direction were presented.
Key words: spatiotemporal database ; trajectories of moving objects; index
因为出现许多需要有效对移动对象管理的应用,STDB受到很多关注。这些应用需要在不同的时间戳记录对象的地理位置(有时也记录对象的形状),而且支持对它们历史的和将来预期的特征进行查询。
STDB的目的是根据数据的时间属性作历史性和预言性的检索。具体地说,给定对象集合o1, o2,… , oN(N是基数),对于每个对象oi(1≤i≤N),历史性STDB会存储oi在历史的所有时间戳t的有效范围oi.E(t)。根据空间数据库的原理,oi.E(t)能够表示为一个描述对象在时刻t的真实形状。尤其是,如果其形状不是重要属性,oi.E(t)则以一个点代替以表示oi在时刻t的位置。实际上,在连续时间戳,同一对象的有效范围可以用不同的方法压缩(例如:如果对象在几个连续时间戳保持静止,则它的有效范围在该时间内只需存储一次)。
另一方面,对每个对象oi,预期性STDB会存储它的最新更新的位置oi.L(tupd)(tupd:对象最新更新的时间)和用于描述它当前移动特性时间函数。最适合的时间函数是线性函数,因为1)线性函数能够近似描述任何运动轨迹,2)线性函数要求的参数个数最少。具体来说,除了oi.L(tupd),系统只需记录对象的速度oi.vel,就可以计算出在将来任何时刻t>tupd对象的位置:
oi.L(t) = oi.L(tupd)+oi.vel(t-tupd)
用这种模型只需在对象的时间函数的参数(如:速度)发生变化时采取更新数据库。
人们已经对作为支持时空查询的辅助结构的时空索引方法做了很多研究。时空存取方法主要集中在两个正交方向:1)对对象过去位置的索引,2)对现在的位置和将来预期位置的索引。
1 移动对象历史数据的时空索引
考虑到移动对象连续不断发送它们的位置,保持所有的更新几乎是不可能的。有两种方法可用来减少历史数据:1)采样,对数据流在某一时刻进行采样。可以采用线性插值计算出相邻采样点间的线性轨迹。2)仅在变化时更新,移动对象仅当它们的数据属性(速度或方向)发生变化时才发送数据。我们把对历史数据的时空索引机制分为三类。
第一类是在现存的空间索引方法加入时间属性。这类时空索引方法主要是处理空间维,时间维是第二要素。
RT-tree[1]结合了作为空间存取方法的R树和作为时间存取方法的TSB树。在RT树中,时间和空间信息是分开维护的。不管是叶结点还是非叶结点,每个索引项都包含(S,T, P) 形式。S是空间信息,T是时态信息(时间间隔), P是指向子树或对象的指针。随着时间变化,如果对象空间位置不变,则它的空间信息S不变,仅对时态信息进行更新。如果对象空间位置发生变化,则需要创建一个新的索引项插入RT树。这种方法有许多局限性,一方面,如果变化对象的数量很大,许多索引项被创建,RT树会迅速膨胀;另一方面,当结点溢出时,怎样分裂结点还没有很好的解决办法。
3D R-tree[2]把时间看作除了空间维以外的另一维。主要思想是为了避开时间和空间查询之间的区别。3D R-tree可以直接利用现有的R树算法来处理空间及时态查询而无需修改,其前提是必须知道移动对象历史轨迹存在的有效时间范围,如果移动对象轨迹结束时刻不确定,那么3D R-tree将无法有效工作。比如若移动对象运动轨迹从某个历史时刻开始一直延伸到当前时刻,显然包围移动对象轨迹的3D MBR将会非常巨大且造成空间区域的大量重叠,直接导致3D R-tree的查询搜索性能下降。因此,在应用中要求移动对象轨迹是封闭的(closed),即移动对象历史轨迹必须在某个过去时刻终止而不能延伸到当前时刻。由于3D R-tree将时间维与空间维等同索引,时间片查询则必须扫描整个3D R-tree而非在此时间片下的有效子树, 因此性能非常低下。
第二类是同时把空间和时间加入某一结构中,但它们是各自独立的。这是为了使在某一时刻所有有效的空间数据同时在一个索引结构(R-tree)中。最高目标使为每一时间项都建立一个单独的R-tree。这种方法需要很大的存储量。
MR-tree[3]采用了在R-tree的背景下可重叠B-tree的思想。主要思想是避免每个时间戳都有单独的R-tree而引起的存储量过大。通过在连续的R-tree中不存储相同的对象实现减少存储量。作为替代,以不同根结点的链接指向同一结点,而所有的结点项都保存着它们在不同时间戳的值。这种思想对时间片查询来说是完美的。搜索被指向适合的根结点,然后利用R-tree进行空间搜索。然而,它对时间窗口查询的执行是无效的。而且,一个主要的缺陷是存在许多重复项。考虑到这样的情况,在连续两个时间戳仅有一个结点项发生变化,而在这连续两个R-tree的所有其它结点也必须重新复制。
HR-tree与[4]MR-tree非常相似。HR-tree是一种采用重叠技术、将单一版本的结构转换为部分固定结构的高效时空索引结构。该结构为两级索引机制,分别对时空对象的时间信息和空间信息进行索引:1)HR-tree是对事务时间进行索引,它按时间递增顺序将时空对象的时间信息组织为有序表,并将时空对象不发生空间变化的那个时间片作为时空对象的时间信息值;2)用R-tree索引结构为每个时间片的空间对象建立索引,并将R-tree的存储信息(根结点存储地址)保存到对应时间片的时间索引结点中。为了节省空间,相邻时间片的R-tree可能会重叠,即若相邻时间片的R-tree有共同的分枝,则只保存该分枝的一个版本。
第三类是主要考虑时间维索引,其次考虑空间维。第三类方法主要集中在面向轨迹的查询。在此类中处理空间查询处于次要位置。
Trajectory-bundle(TB-tree)[5]是完全保持轨迹的类似R-tree结构。一个叶子结点仅能包含属于同一轨迹的线段。存在一个缺陷:在空间上比较靠近的不同轨迹的线段将被存储在不同的结点上。构建TB-tree是从左到右的原则。也就是说。最左边的结点是最先插入的结点,最右边的结点是最后插入的结点。
Scalable and Efficient Trajectory Index(SETI)[6]将空间区域分割成静态且不重叠的分区,在每个分区下对移动对象的轨迹线段利用R树进行索引。其考虑是,相对于无限连续变化的时间维而言,移动对象轨迹受空间范围所限,那么可以把受限的空间区域利用某种规则静态划分以分而治之。良好的划分函数应尽量把同一移动对象不同轨迹线段聚类在同一个分区中。若一条轨迹线段穿过多个分区,那么必须将此线段裁剪并分别存储在不同分区R树中,这样会导致查询结果的重复,在查询处理后必须进行重复结果的剔出。相应地,时态查询则被转换为对折线段集合的空间窗口查询,利用几何计算方法可以得到空间窗口内的折线段集合,其对应的移动对象集合即是时态查询结果。
2 移动对象当前位置轨迹索引
在现实应用中许多要求能够有效地对移动对象当前位置进行管理和查询。相对来说,检索移动对象当前位置更具有挑战性,其关键在于如何提高传统空间索引的频繁更新动态性能以满足动态环境下的应用要求。标准R树更新算法采用删除-重插机制来实现移动对象位置更新,频繁更新会导致R树性能急剧下降。为了支持R树的频繁更新操作,近年来提出的方法包括LUR树(Lazy Update R-tree)、自底向上更新策略(Bottomup Update)、哈希方法(Hash)等。LUR[7]提出了一种延迟更新(Lazy Update)策略,即若移动对象位置未超出当前节点MBR,算法仅仅更新移动对象所在的数据页面并维持索引页面不变;对于移出MBR之外的移动对象,根据其超出MBR程度大小,判断是否将MBR进行有限扩展以包含移动对象新位置;或者利用标准R树更新算法进行更新以尽量减少位置更新所带来的索引树更新操作。Bottom-up Updates的自底向上法扩展了LUR-tree思想。自底向上法比较适合处理移动对象的连续更新。例如:扩展MBR以包含新的值和移动当前对象到兄弟结点。
Song 等人利用空间划分的思想来索引移动对象当前位置,首先静态地把空间划分为可以相互重叠的区域,然后根据当前位置将移动对象哈希映射到不同区域中去。只有当移动对象位置超出了当前区域才会更新此对象的索引记录,数据库中保存了移动对象位置近似视图。
3 当前和将来轨迹查询索引
在移动计算、位置服务等新兴应用中,需要对移动对象当前及未来位置预测以提供相关服务,针对移动对象当前和未来轨迹的索引方法是目前研究的热点。为了能够预测移动对象未来轨迹,需要存储一些额外的信息(如移动对象当前速度和目的地等)。然后根据移动对象当前的运动特性对未来轨迹进行预测,目前通常使用线性方程来描述移动对象的运动特性。在D维空间下,移动对象运动特性可以使用参考时间tref时位置xref = ( x1,x2,…,xd )以及速度矢量v=(v1,v2,…,vd )来描述。移动对象在任何时间点t (t≥tref )的位置可利用公式xt = xref +v (t- tref )计算得出。主要的索引方法有:FT-Quadtree、PMR-Quadtree、STRIPE索引、TPR-tree、TPR*-tree等。
FT-Quadtree[8]使用的是Quad-tree索引结构,最大的特点是使用了轨迹共享技术来最大限度地减少数据的存储数量,提高索引的更新效率。在这种树中的叶子节点结构表示为(oid,轨迹的数量,起始坐标,结束坐标,起始时间,结束时间,其他信息)。对于在同一时间内的节点而言,如果它们的坐标位置相同或者接近,那么就可以采取共享策略把若干个节点的内容放入一个公共的节点内,这样就可以明显地减少存储的空间。
使用PMR-quadtree[9]作为索引将来轨迹的基本空间存取方法,关键的一点是当移动对象发生更新时,整个索引结构被破坏,然后根据新的信息重建索引结构。为了避免过多的更新操作,索引每ΔT时间单元重建。在理论上,无限的时间维可以分割为大小为ΔT的相等的时间片。对于每一时间片,会构建一个新的基于运动方程的PMR-tree。然而,由于存储设备的有限性,只有当前的PMR-tree会被存储。
TPR-tree[10]使用时间参数化包围框来包含移动对象,其索引结构与R树类似。但TPR-tree采用谨慎的BR策略,在某些时刻(如构建时刻)包围框是最小的,但在其后的时间内往往不是。从一维角度考虑,MBR最(大)小边界速度为其范围内所有点的最(大)小速度,从而保证所有点始终包含在同一个MBR中。TPR-tree索引节点记录不仅存储了移动对象(子树)MBR,而且包含了移动对象(子树)MBR速度矢量。由于节点MBR呈现出一种随时间变化的动态性,随着时间延伸包围框会越来越大,导致空间区域的大量重叠从而使得性能下降。因此,必须在适当时候对TPR-tree进行重构以提高查询性能。
TPR*-tree[11]修改了TPR-tree的动态操作算法。通过维护一个代价下降优先队列保证插入路径选择的全局最优,保持TPR-tree MBR的紧致性以提高查询性能。对于上溢节点的分裂算法,TPR*-tree只是在必要的时候才对节点分裂并重插。以二维空间移动对象为例,节点首先在所有可能的8个方向(4×d)上进行排序,并从中选择一种最好的分裂方式,实际上此时节点并不分裂,而是把节点中30 %的记录删除后重插。如果在重插过程中发生上溢,那么就直接进行节点分裂以避免传递操作。TPR*-tree是目前最好的参数化空间访问方法。
4 结束语
该文总结了移动对象轨迹索引的各种技术,并对它们进行了比较详细的分类,对每种方法均找出了多个比较典型的模型进行介绍。近年来对移动对象历史轨迹、当前位置与未来趋势预测的索引方法研究较多,在如何同时解决上述三种查询的索引方法上研究仍然欠缺。多种索引结构的结合是时空数据库系统实际设计的主要趋势,选择哪几种索引结构以及如何把它们有机地结合起来将是系统设计所面临的主要难题。
参考文献:
[1] Xu X, Han J, Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases. In Proc. of the Intl. Symp. on Spatial Data Handling, SDH, pages 1040C1049, July 1990.
[2] Basch J, Guibas L J, Hershberger J. Data structures for mobile data. In Proc. of the ACM-SIAM symposium on Discrete algorithms, SODA, pages 747C756, 1997.
[3] Xu X, Han J, Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases. In Proc. of the Intl. Symp. on Spatial Data Handling, SDH, pages 1040C1049, July 1990.
[4] Nascimento M A, Silva J R O. Towards historical R-trees. In Proc. of the ACM Symp. on Applied Computing, SAC, pages 235C240, Feb 1998.
[5] Pfoser D, Jensen C S, Theodoridis Y. Novel Approaches in Query Processing for Moving Object Trajectories. In Proc. of the Intl. Conf. on Very Large Data Bases, VLDB, pages 395C406, Sept. 2000.
[6] Chakka V P, Everspaugh A, Patel J M. Indexing Large Trajectory Data Sets with SETI. In Proc. of the Conf. on Innovative Data Systems Research, CIDR, Asilomar, CA, Jan. 2003.
[7] Kwon D, Lee S, Lee S. Indexing the Current Positions of Moving Objects Using the Lazy Update R-t ree[C]// In :Proc. of MDM,2002.
[8] Ding R, Meng X F, Bai Y. Efficient Index Maintenance for Moving Objects with Future Trajectories[C]// Kyoto: The 8th International Conference on Database Systems for Advanced Applications(DASFAA), 2003. 183.
[9] Tayeb J, Ulusoy O, Wolfson O. A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal,41(3):185C200, 1998.
数据库索引范文第2篇
作者简介:刘波（1983-）,男，河南信阳人，博士研究生，主要研究方向：分布式实时数据库、卫星遥感信息处理； 范士明（1945-）,男,上海人，研究员,硕士,主要研究方向：卫星遥感信息处理； 刘华（1969-）,男,重庆人，高级工程师,硕士,主要研究方向：卫星遥感信息处理。
文章编号:1001-9081（2011）08-02265-05doi:10.3724/SP.J.1087.2011.02265
（中国航天科技集团公司第五研究院 五零三研究所，北京100086）
（.cn）
摘 要:在卫星地面设备监控中，需要将大量实时数据实时地存进数据库并提供实时查询。针对实时数据和Judy array数字树的特点，提出了一种基于内存映射文件的位图分配法，然后设计了一种哈希表、B+树和Judy array混合索引机制。通过大量记录的插入和查询，结果表明位图分配法能避免大量不可利用的内存碎片的产生，结合内存位图分配法的混合索引机制也为应用程序提供了实时的索引插入和查询。
关键词:实时数据库；位图分配法；内存映射文件；哈希表；B+树;Judy array
中图分类号: TP311.131文献标志码:A
Design and implementation of hybrid index mechanism for real-time database
LIU Bo, FAN Shi-ming, LIU Hua
（503 Institute, the Fifth Academy of China Aerospace Science and Technology Corporation, Beijing 100086, China）
Abstract: It is necessary to store massive real-time data into database and query records from database in real-time on the field of satellite ground device monitoring. Taking account of the characteristics of real-time data and Judy array, a bitmap memory allocation method based on memory map file was proposed. A hybrid index mechanism which employed Hash table, B+ tree and Judy array was designed. Through insertion and querying of massive records, the experimental results show that bitmap allocation method avoids the generation of massive tiny memory holes. Being combined with bitmap allocation method, the hybrid index mechanism provides real-time index insertion and record querying for applications.
Key words: real-time database; bitmap allocation method; memory map file; Hash table; B+ tree; Judy array
0 引言
卫星地面设备监控系统需要对大量数据信息进行采集、传输、综合分析、计算等处理。从监控系统组成可以看出，数据是联系各功能模块的纽带。随着卫星地面应用系统的发展，地面设备监控系统的功能需求也不断增多、增强，数据量也不断扩大，数据之间的关系也越来越复杂。因此需要将数据库技术引入卫星地面设备监控，用数据库技术来管理、处理监控过程中的数据。但卫星地面设备监控中数据的一个显著特点是具有时间特性，且有效时间是短暂的，过时则失效。而以关系数据库为代表的传统数据库的设计目标是维护数据的正确性、保证系统的低代价和提供友好的用户接口。这种数据库系统对传统的商务和事务型应用是有效、成功的，但对于新领域的实时数据和实时事务的应用要求难以胜任。所以，需要结合数据库技术和实时技术，研究具有显式定时限制的实时数据库系统［1］。
键值（key-value）型索引性能的好坏直接影响实时数据库的稳定性、可靠性、实时性。在卫星地面设备监控中，实时数据库将面临超大量的实时数据，最新的实时数据必须能在一定时间内存入数据库，相对陈旧的历史数据在给定key时必须能在一定时间内检索到相应的值。传统的键值型索引并没考虑到这种超大量实时数据的特点，导致其在内存空间的利用效率、索引插入和查询的实时性上很难达到要求。对此本文根据地面设备监控中实时数据的特点以及检索要求，采用内存映射文件技术处理数据文件的读取，提高了数据文件的I/O读写速度；利用位图分配法代替操作系统的内存分配，可以避免大量内存碎片，提高数据库文件存储空间的利用率；采用混合索引取代数据库中常用的哈希表、B+树、T树索引机制，实现了索引压缩和有序存储，并保证记录的实时插入和查询。
1 基于内存映射文件的位图分配法
1.1 内存文件映射机制
内存映射文件允许在进程的虚拟地址空间中保留一段内存区域，并将物理存储器中的目标文件提交给该区域，映射到这段虚拟内存之中。这样，物理存储器来自一个已经位于磁盘上的存储近期实时历史数据的文件，而不是系统的页文件。一旦该文件被映射，就可以用存取内存数据的方式直接操作文件中的数据，就像整个文件已经被加载到内存中一样。因此使用内存映射文件处理存储在磁盘上的文件时，将不必再对文件执行I/O操作，这意味着对文件进行处理时将不必再为文件申请并分配缓存，所有的文件缓存操作均由系统直接管理，由于取消了将文件数据加载到内存、数据从内存到文件的回写以及释放内存块等步骤，使得内存映射在处理实时数据库这种有着大数据量的文件时有显著的优势。
实时数据库必须作为多个进程共享数据的仓库。内存映射文件正是计算机操作系统提供的解决多个进程间共享数据的最有效方法。数据共享通过让多个进程映射同一文件内核对象的视图来实现的，这意味着进程间将共享物理存储器中的同一个数据库文件。因此，当一个进程将数据写入一个共享文件映射对象的视图时，其他进程可以立即看到它们视图中的数据变更情况。同时，内存映射文件将作为数据库持久存储的手段。当事务提交时，如果内存中相应于磁盘文件的页面发生了改变，调用操作系统的内外存交换机制，将事务对数据库的更新操作保存在磁盘上。此时持久化到磁盘上的文件将作为数据库的后端备份，一旦应用程序出错或掉电导致内存数据丢失时，磁盘文件将被重新映射，使数据库能尽可能快地从故障中恢复过来。
1.2 位图分配法
实时数据库系统中，内存分配要求实时高效。本文借助位图［2-3］实现内存分配，根据系统配置大小设定共需多少个位图页面，每个位图页面为4KB，因此共有32K比特位，每个比特位可分配8B（也可以不是8B，可根据系统配置要求而定）。如果该位为0，表示该比特位代表的相应位置的8B尚未分配，否则相应位置的8B已分配出去，因此一个位图页面可分配的空间为256KB。文件头包含数据库文件的描述信息，页面地址分别指向各自的位图页面首地址，n个位图页面连续集中在一起，可减少因位图页面过于分散而导致的内存碎片较多的问题。每个位图页面负责其分配的区域，如位图页面0负责分配第一个256KB，位图页面1负责分配第2个256KB。
1）位图页面内寻找可分配空间过程。
如下代码所示，其中pos以字节为单位,i表示正搜寻的位图页面编号（从0开始）；offs指当前位图页面搜寻的起始点，以字节为单位，其范围是（0,…,4K-1）；mask为offs位置上的值，单字节长度；holeBitSize指目前搜寻到的连续的比特0数目；size指请求分配的字节数，objBitSize指分配size所需比特数；PageSize是页面大小，4KB；firstHoleSize［mask］指mask中从最低位往最高位数起的第一个连续比特0个数；maxHoleSize［mask］表示mask中最多的连续比特0个数，代表可分配的最大空间；maxHoleOffset［mask］为最多的连续比特0个数区域在mask中的位置；lastHoleSize［mask］表示从最高位往最低位数起的连续的比特0个数；mask的值为（0,…,255），它们有各自的firstHoleSize、lastHoleSize、maxHoleSize、maxHoleOffset。
if（holeBitSize+firstHoleSize［mask］）≥objBitSize{
pos8×（（i×PageSize+offs）*8-holeBitSize）;
如果从pos开始size大小的区域尚未保留,保留这片区域,将位图页面中pos开始size大小的相应位全置1,然后撤销保留区域，内存分配成功,返回pos；否则,offs增加（objBitSize+7）/8,holeBitSize置0,继续搜索可分配空间
}else if（maxHoleSize［mask］≥objBitSize）{
pos8×（（i×PageSize+offs）×8-maxHoleOffset［mask］）;
如果从pos开始size大小的区域尚未保留,保留这片区域,将位图页面中pos开始size大小的相应位全置1,然后撤销保留区域，内存分配成功,返回pos；否则,offs增加（objBitSize+7）/8,holeBitSize置0,继续搜索可分配空间
}else if（上述两条件都没有满足）{
如果lastHoleSize［mask］等于8,将holeBitSize加8；否则将holeBitSize设置为lastHoleSize［mask］
offs加1;
}
如果offs≥PageSize,这时搜寻到下个位图页面,置offs为0,i加1
2）扩展位图页面过程。
当搜寻全部位图页面后，还没能找到指定大小的空间，则需要增加新的位图页面，此时等于扩展可分配的内存空间。extension为新扩展的内存空间大小，morePages为重新开辟的位图页面数目，n是未扩展前系统中已有的位图页面个数。扩展内存空间通过增加新的位图页面完成，为减少内存碎片，也为了确保未扩展前已搜寻到的holeBitSize个比特0位同新扩展空间中的objBitSize个比特0位连续，在新位图页面前添加若干内存页面（如果holeBitSize为0，不必附加这片空间）。附加的内存页面个数skip（objBitSize×8）/PageSize。当扩展完成后，找到足够空间，返回刚分配空间的起始地址pos（以字节为单位）。当holeBitSize不为0,因找不到足够大小的空间而引起的内存扩展过程描述如下所示：
1）令morePages为满足morePages×PageSize×64≥extension+morePages×PageSize的最小整数,将objBitSize减去holeBitSize;
2）令skip为满足skip×PageSize≥objBitSize×8的最小整数,置pos为n×PageSize×64+skip×PageSize;
3）将数据库表文件中范围为［0,pos+morePages×PageSize］的部分重新文件映射;
4）置pos位置后从第1到第objBitSize个比特位为1,置从第PageSize×skip/8个比特位开始的morePages×PageSize/8个比特位为1；
5）将每个位图页面的首地址赋给相应的位图页面,令pos为（n×PageSize×8-holeBitSize）×8,并将［pos,pos+holeBitSize×8］这段区域在位图页面中的相应比特位置1。
2 Judy array数字树
通常情况下,数字树［4］根据索引的范围划分为层次树，当插入或删除索引时，不需要对树进行平衡操作；对索引的查找、插入、删除等操作的执行时间依赖于索引本身，而不依赖于整棵树的节点个数。数字树的每个节点都是一数组，不同层的数组存储索引的不同连续N位信息。数字树的缺点在于当数字树的分支较多时，空指针的相对比例较高，树的内存利用率较低；另一方面，当树的分支较少时，虽然空指针的相对比例降低，树的内存利用率高，但当操作某个索引时，分支较少的数字树需更多的指针来定位value，这将导致不能充分利用程序的局部性原理，使得CPU高速缓存（cache）的命中率降低［5］，大大减缓了指令执行速度。
Judy array［6-7］采用一种压缩256阶数字树（即数字树的每层存储的是索引的一字节），根据节点内部存储的索引个数自动调整节点内部结构和树本身结构，达到压缩节点节省内存的目的。节点的自适应压缩通过如下方式：1）当前范围索引数较少时，节点压缩为线性节点或位图型节点。2）“窄节点指针”指向的叶子节点或分支节点能跨越多层，即节点中索引的公共字节部分可以存放在“窄节点指针”里。3）借助“立即指针”，将索引直接存储在分支节点里;同时所有调整是自适应的，不需要辅助参数对其进行性能上的优化调整。
2.1 分支节点、叶子节点
Judy array数字树有如下5种节点。其中线性叶子节点可存储多字节（指索引中未解码的字节个数）索引，位图叶子节点只能存储1字节索引。线性叶子节点溢出时会转换成位图叶子节点，这种转换仅发生在索引中剩余的未解码部分还剩一字节时。位图被均匀划分成8部分，每部分由32个比特位构成，其中如果有任一比特位为1，则有一指针指向存储了索引相应信息的数组，否则该指针为空。因此必须依据位图的比特位信息获得索引在数组中的偏移。
1）线性分支节点。第1个字节存储当前数组中存储的有效索引的数目，后面7字节存储包含索引的子范围的编号（0到255之间），接下来的56字节存储至多7个“节点指针”，用于指向树的下层叶子节点或分支节点。
2）位图分支节点。首先存储256个比特位，用比特位0或1表明相应的子范围是否包含有效索引，如果没有用0表示，反之用1表示。接下来是8指针，分别指向至多存储了32个“节点指针”的数组，依据数组元素多少，数组大小分别为2,4,6,8,12,16,24,32,48,64个word。
3）未压缩分支节点。包含了256个“节点指针”的数组，“节点指针”指向下层的叶子节点或分支节点，该分支节点占用2048B空间。
4）线性叶子节点。当前叶子节点包含的索引个数及索引字节数（1到3字节）存储在指向叶子节点的“节点指针”里，首先存储若干索引，然后存储每个索引对应的值域，值域中存放指向值的指针（对于大于4字节的值）或是值本身（小于等于4字节的值）。
5）位图叶子节点。只有当节点中未解码字节数剩1时，线性叶子节点才会转化为位图叶子节点。类似位图分支节点，指针为普通指针，每个指针指向存储了值域的数组，该数组类似位图分支节点中的数组，不同的是它存储索引相应的值。
2.2 “节点指针”
“节点指针”指向树的分支节点或叶子节点，占2word。“节点指针”中的1word是普通指针，用于指向下层节点，D域（存储索引集合中公共字节）和P域（存储的索引个数）共占3字节，T域（“节点指针”类型）占1字节，它们共同占用1word。“节点指针”总驻留在分支节点里，所以索引的首字节已经确定，其尾字节在叶子节点中也可确定，因此分支节点所指索引集合的公共字节个数至多为2（针对32位平台，64位平台为6）。D域和P域的界限是浮动的，当“节点指针”所指节点层次低时，P域字节少，D域字节多；当节点层次高时，P域字节多，D域字节少，32位平台上3字节足够存储D域和P域。
“窄节点指针”指的是跨越了多个层次的“节点指针”，其D域中存放了索引集合的公共字节。“节点指针”可不指向叶子节点或分支节点，能直接将索引存放在“节点指针”里，这种存放了索引的“节点指针”称为“立即节点指针”。“立即节点指针”只能存储非常少量索引，32位平台上“立即节点指针”只能存储一个3字节的索引。当插入索引引起“立即节点指针”溢出时，它转换成一指向叶子节点的“节点指针”，这时叶子节点存放的是原先存储在“立即节点指针”里的索引和新插入的索引。
2.3 插入索引过程
下面描述了当插入索引时Judy array的节点变化过程，删除索引等同于插入索引的逆过程。
1）空的根指针指向没有存储任何索引的数字树。
2）插入第1到31个索引时，根指针指向单个树根叶子节点（树根叶子节点与线性和位图叶子节点不同，但结构类似于线性叶子节点）。依据索引个数不同，树根叶子节点分别需占用2,4,6,8,12,16,24,32,48,64个word空间。
3）当树根叶子节点溢出时，即插入索引个数大于等于32时，叶子节点转化为分支节点，分支节点存储若干“节点指针”，“节点指针”指向下层分支节点或叶子节点或直接存储索引。
4）当“立即节点指针”溢出时，它转换为普通“节点指针”，指向线性叶子节点。当进一步插入更多索引时，它可能会转换为一指向位图叶子节点的“节点指针”（只有当线性叶子节点存储的是1字节索引时才可能转换为位图叶子节点）。
5）当插入索引导致叶子节点溢出时，算法检查是否可将叶子节点中的索引和新插入的索引压缩存储在当前叶子节点，因为索引字节数减少，叶子节点可容纳更多索引。这时其“父节点指针”将转换为“窄节点指针”或者当“父节点指针”原先就是“窄节点指针”时将转换为“更窄”的“节点指针”，图1展示了32位平台上数字树的某一“节点指针”转为“窄节点指针”的过程。
图1 “节点指针”转化为“窄节点指针”示例
6）随着索引的更多插入，导致存储2～4字节（针对32位平台）索引的线性叶子节点溢出时，如果它不能降低自身层次而成为“窄节点指针”所指的线性叶子节点，那么会生成一新的分支节点，将新节点插在父“节点指针”和线性叶子节点间，这时线性叶子节点会分裂为至少两个节点，如图2所示。一般情况下新插入的分支节点将是线性分支节点，但如果先前的线性叶子节点中的索引具有较大随机分布性质时，新插入的分支节点将可能是位图型分支节点。
图2 线性叶节点分裂为低层叶节点示例
7）当插入新索引到“窄节点指针”所指的叶子节点或分支节点时，如果新索引对“窄节点指针”所指节点是“外来者”（即新索引在“窄节点指针”能表示的范围之外），算法生成一新的线性分支节点，将其插入在“窄节点指针”和“窄节点指针”所指节点之间，新插入索引将作为一“立即节点指针”而存放在新的线性分支节点里，此时新的线性分支节点具有两个分支。图3展示了在64位平台上插入新索引到“窄节点指针”的过程。
图3 插入“窄节点指针”示例
3 混合索引机制
数据库表只能逐行访问，如果要快速访问表格中记录，需对表中记录建立索引。对卫星地面设备监控中需存储的实时数据的查询形式非常固定：即从时刻ts起，到时刻te结束，时间间隔为tspan，采集点集合S{S1,S2,…,Sn}在所有时刻的值。因此本文用哈希表、B+树［8］和Judy array数字树来建立索引，索引关键字为设备采集点描述符与设备采时刻，索引值为相应实时记录的oid。
当为某采集点的实时记录建立索引时，首先根据采集点的设备描述符在哈希表中找到采集点的B+树，然后以实时记录的采集时刻作为关键字在B+树中插入索引，如图4所示。本文的B+树叶子节点中有两种索引：一种是立即索引，直接与记录关联；另一种是压缩树索引，指向一棵Judy array压缩树。压缩树记录占若干页面，随索引插入，压缩树会频繁地删除或生成内部节点，为此本文以位图法管理压缩树内部空间的分配和删除。如对64KB大小的压缩树，可在页面首地址处以1024B（1B代表8b）管理整个页面空间。当索引关键字是严格递增顺序时，采集点的树建立索引过程描述如下。
图4 混合索引示意图
1）初始时B+树的高度为1，随着索引陆续插入节点，该节点将溢出。溢出时节点不像普通B+树节点会分裂成两个节点，而是在数据库表中插入一新的Judy array数字压缩树记录，将叶子节点的全部索引转存进压缩树中，并将该压缩树索引插入到B+树叶子节点里。
数据库索引范文第3篇
【关键词】XML 1-index F&B索引
可扩展标记语言XML（eXtensible Markup Language）是一门新兴的面向Internet应用的标记语言，是为在WEB上使用而优化的SGML子集。XML是一种简单、与平台无关并被广泛采用的标准，是用来定义其它语言的一种元语言。XML具有强大的描述能力，又有适应网络应用的简洁性，作为对SGML语言标准的一种改良，XML具有适于异构应用间数据共享，可以进行数据检索和提供多语种支持等特点。
XML及其相关技术的研究不仅在数据库理论领域占有一席之地且其水平已成为衡量一个国家信息化程度的重要标准之一。目前很多XML索引技术已被提出，具体可以分为：
（1）基于路径的XML索引方法，如DataGuide、1-index、A （k） 索引、D（k）索引、F&B索引等。
（2）基于编码的XML 索引方法，如Anc_Desc_B + 、XR + XRStack 算法等。本文主要介绍了1-index以及F&B索引。
1 1-INDEX
为了解决DataGuide 的上述两个问题，1-index提出“bisimulation”和“simulation”的概念。1-index 索引中将“相似”的节点存放在一个扩展集中，这可能造成DataGuide 中所有扩展集的节点总数是XML 数据图中节点总数的指数倍。两节点“相似”概念使得1-index 具有如下两个优点：
（1）索引大小和XML数据图大小成线性关系。
（2）索引的扩展集之间不相交，所有扩展集的节点总数和XML 数据图中节点总数相等。
2 F&B索引
DataGuide 和1-index 保存XML 数据图中所有边的信息，可称为“覆盖索引”，因为它们可以直接通过索引进行查询而不必访问原来的数据。在本文里我们称child axis 为PC axis，descendant-or-self 为AD axis，我们称没有分支谓语的或AD axis为简单路径。DataGuide 和1-index只能进行简单路径查询，因此提出了the forward-and-backward index，简称F&B索引可以被视为分支路径表达式查询的“覆盖索引”。在所有的XML索引中，F&B索引是可以回答条件约束的最小索引。F&B索引是已有的XML索引中最有效、最强大的一种，F&B索引技术在不断的改进。
基于路径索引的XML 查询方法只能够解决单路径查询，但路径索引的创建不受XML文档结构的约束，即XML 文档可以是树结构，也可以是图结构。基于编码方式下的XML 索引查询方法能够有效地解决分支路径查询，但是这种方法都对相应的XML 文档有要求，其所要查询的XML文档为树形结构。
DataGuide的提出解决了这一问题。但是DataGuide仅限于一个常规表达式的查询，对于多个表达式的复杂查询不起作用。针对已提出的索引结构的不足，Tova Milo和Dan Suciu提出了模板索引。与以前的方法相比，T-INDEX有以下几方面的改进：
（1）使交换空间普遍化。
（2）“bisimulation”和“simulation”的提出使索引可以有效的建立。
（3）索引的大小有保证。
（4）与DataGuide相比它是一个完美的一般化的索引结构。
1-index和2-index是模板索引的两个特殊的索引，模板索引是1-index和2-index的概括和一般化。
对于每个在DB中的节点v，用Lv（DB）或Lv表示从根节点到节点v的路径字符集合：Lv（DB）={w|w=a1…an}， ? a path v0 …{v， v0 是根节点}。在DB中的节点vu则vu?Lv=Lu，我们用[v]来表示v的等价集合。
这种方法效率低，有两个原因：
（1）计算等价类需要花费大量的时间。
（2）等价类之间存在重叠，浪费空间。为了解决构建开销问题，提出改进：v≈u?vu。1-index索引中提出了“bisimulation”和 “simulation”的概念。
DB是一个数据图。节点间的一个二进制关系 ～是一个backwards bisimulation满足以下四点：（1）如果v～v’和v是根节点，那么v’也是根节点；（2）相反的，如果v～v’和v’是根节点，那么v也是根节点；（3）如果v～v’，那么对于任意边uv存在一个边u’v’，满足u～u’；（4）相反的，如果v～v’，那么对于任意边u’v’存在一个边uv，满足u～u’。
通过广度遍历函数Bfsl（）对树进行层次遍历，然后通过merge（）函数对祖先节点相同的同层节点进行合并将XML数据建立成1-index树，然后再通过Dfsl（）函数对1-index树进行前序遍历，对树的每个节点存储两个数值id和level。id用来表示它被遍历的次序，level用来表示它所在的树的层数。
3 结论
本文研究了XML存储与索引技术，主要研究了两种索引：
（1）板索引中的1-index。
（2）于磁盘的F&B索引。
1-index提出 bisimulation和simulation，索引大小和XML数据图大小成线性关系，索引的扩展集之间不相交，所有扩展集的节点总数和XML 数据图中节点总数相等。但1-index只适合查找固定常规表达式，对于多分支的表达式则不能准确地查找。F&B索引是目前XML索引中最强大的一种，它以最小的索引覆盖所有分支。
参考文献
[1]刘雨洋，李建中，王宏志等.于后裔聚集F&B索引的XML数据查询处理算法[J].计算机科学，2006，33（11）：363-365.
[2]孔令波，唐世渭，杨冬青.XML数据的查询技术[J].Journal of Software，2007， 6（18）：1400-1418.
[3]刘显敏，李建中，王宏志等.SAJ：以最小化空间代价为目标的F&B索引构建算法[J].计算机研究与发展，2006（43）：413-417.
数据库索引范文第4篇
关键词：海洋环境；数据库系统；Oracle；性能优化
中图分类号：TP311.13
对于传统数据库系统进行优化一般遵循“数据库配置优化”―>“数据库应用优化”的顺序原则。而船载海洋环境数据库系统是单用户、单任务系统，I/O操作并不是很频繁，在系统结构设计合理的情况下，对数据库配置的优化效果并不十分明显，同时许多优化专家认为对应用程序的优化可以得到80%的系统性能的提升。因此，数据库应用优化成为了船载海洋环境数据库系统性能优化的关键技术。
本文将以Oracle优化技术为基础，针对特殊需求，对船载海洋环境数据库系统进行应用程序优化技术研究，提出性能优化关键技术，实现数据库系统性能优化。
1 系统功能特点
2 性能优化技术研究
通过功能分析，针对实际需求，研究的工作重点为基于应用程序层面的SQL语句优化技术和索引技术。
2.1 SQL语句优化技术
应用程序对数据库的操作最终表现为SQL语句对数据库的操作[1]。对于船载海洋环境数据库系统而言，SQL语句是对海洋环境数据库进行操作的惟一途径，它消耗了70%～90%的数据库资源，SQL语句的执行效率直接关系着船载海洋环境数据库数据查询的速度与效率。
针对查询操作，SQL语句优化的方法有：
（1）尽量使用占位符代替变量；
（2）where子句限定条件的放置顺序应与索引字保持一致；
（3）选择最有效率的表作为基础表；
（4）避免采用MATCHES和LIKE通配符匹配查询；
（5）避免或简化排序；
（6）避免非开始的子串；
（7）避免相关子查询；
（8）消除对大型表行数据的顺序存取；
船载海洋环境数据库系统应用主要应用体现为海量数据信息的嵌套查询，该模式工作效率的致命影响因素主要归结为对大型表行数据的顺序存取。以查询潮流表中2012年3月的平均潮高信息为例，如果采用顺序存取策略，该查询操作即为三层嵌套查询操作，假设每层仅查询300行，该查询操作仍会产生遍历3亿行数据的庞大工作量。研究发现，为避免该情况发生，我们可以建立索引在连接的字段上。例如，对索引表（年、月、层、……、表名）和统计数据表（表名、经度、平均值……）这两个表进行跨表连接查询时，两个表建立连接，应建立索引在“表名”这个连接字段上。
此外还可以使用并集来避免顺序存取。即时建立索引在全部查询列，然而where子句会自动强迫优化器忽略全部索引而进行顺序存取查询。例如，下面的查询将会强迫对orders表执行顺序操作：
（9）对于大数据量的求和避免使用单一的sum命令处理，可采用groupby方式与其结合；
（10）避免可能会引起磁盘读写的rowid操作。
（11）使用临时表加速查询。
此外，可以使用Oracle提供的SQLTrace工具和EXPLAINPLAN命令来进一步调整SQL代码。
SQLTrace提供解析、执行和返回数据次数；执行SQL语句所花CPU时间和执行语句经历的时间；处理的记录数和库缓冲区错误次数等有用信息。
EXPLAINPLAN命令可显示Oracle优化器为SELECT、UPDATE、INSERT和DELETE语句选择的执行计划[2]。
2.2 索引优化技术
索引的主要作用是提高索引数据的效率。合理地使用索引、优化数据检索是提高数据处理速度的一个重要方面。
Oracle中常用的索引类型是B-Tree索引。
2.2.1 B-Tree索引
B-Tree索引是按B数结构组织并存放索引数据的。该索引结构是一棵平衡二叉树。以海洋环境数据库中海面气温要素客观分析数据为例，其B-Tree结构示意图如图2所示。最顶层的索引块为根，包含指向分支节点的信息；中间为分支节点，包含指向下级分支部分和指向叶子节点的信息；最底层索引块为叶子节点，包含索引列和指向表中每个匹配行的ROWID信息。叶子节点是一个双向链表，因此可以对它们进行任何方面的范围扫描。
2.2.2 使用索引时应注意的问题
尽管在一个表上建立索引可能会加快查询的速度，但是也必须注意到它的代价：
（1）索引会降低DML操作的速度[5]，因为每一条DML语句只要涉及到索引关键字，Oracle系统就得调整索引，这意味着每当有记录在表中增减或索引列被修改时，索引本身也会被修改并改变存储次序，从而多占用CPU和磁盘I/O等系统资源。
（2）索引作为一个独立的对象需要消耗磁盘空间，如果表很大的话，其索引消耗磁盘空间量也会很大。
因此，使用索引时一定要认真分析数据的构成、经常使用的查询数据列和条件列，仔细选择索引列和列的组合，切忌对数据量需要频繁更新的列建立索引[6]。同时，还要根据数据产生和使用的不同阶段，适时打开或关闭某些索引，以优化数据查询和处理。
通过以上对比，说明优化原则是有效的，应用优化原则可以使查询速度加快。通过大量实验证明当测试数据的数量及数据表的项数足够多时，查询速度提高的幅度极其明显，对于一个六百万左右的数据查询显示优化前需要60s，优化后只需要12s左右。
3.2 索引优化测试
索引的访问分为索引唯一扫描和索引扫描范围两种模式。船载海洋环境数据库系统主要应用的是索引唯一扫描模式。在SQL语句中，优化器常通过where子句访问索引。
以海洋环境数据库中潮流要素为例进行优化实验。
在这里定义了一个二级索引机制，先从索引表中通过组合索引查询到相应的数据表名，然后将该数据表名以变量形式嵌入查询语句中，并与num列唯一索引组合作为二次索引，这样大大加快了数据查询的效率。
同时，由于该SQL语句是用在海洋环境查询显示界面，进行以上处理后，可以加快数据显示的速度。
4 结论
本文通过分析船载海洋环境数据库系统功能特点，针对其需求特点，提出了性能优化关键技术SQL语句优化技术和索引技术。使用这些关键技术成功地进行了海洋环境数据库系统性能的调整和程序的优化，从而有效地提高了数据查询显示的速度，更好地保障了海洋环境数据的安全性和可靠性，为船舶的海上航行提供了必要的决策支持，具有一定的实际应用价值。
参考文献：
[1]袁爱梅.Oracle数据库性能优化研究[D].华东师范大学，2007.
[2]高艳春，周兆确，唐艳军.Oracle性能调整与优化[M].北京：人民邮电出版社，2002.
[3]路川，胡欣杰.Oracle10g宝典[M].北京：电子工业出版社，2008.
[4]毛选，魏海萍，孙思云.OCP：Oracle9i性能调整学习指南[M].北京：电子工业出版社，2003.
[5]何致亿.Oracle9i实务管理讲座――系统核心篇[M].北京：电子工业出版社，2003.
[6]Oracle.Oracle9iDBAFundamentalsIIVolume1StudentGuide[M].2002.
[7]高峰.基于Linux的船载海洋环境数据库系统设计与实现[D].哈尔滨工程大学，2008.
[8]肖军.ORACLE数据库性能调整与优化[D].武汉大学，2004.
[9]李捷.短信系统中的Oracle数据库性能优化及实施[D].重庆大学，2007.
数据库索引范文第5篇
[关键词]B树；索引；数据库管理软件
中图分类号：TQ1 文献标识码：A 文章编号：1009-914X（2014）23-0252-02
1 引言
索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。表的存储由两部分组成，一部分用来存放数据页面，另一部分存放索引页面。通常，索引页面相对于数据页面来说小得多。数据检索花费的大部分开销是磁盘读写，没有索引就需要从磁盘上读表的每一个数据页，如果有索引，则只需查找索引页面就可以了。所以建立合理的索引，就能加速数据的检索过程。
数据库索引就是加快检索表中数据的方法。数据库的索引类似于书籍的索引。在书籍中，索引允许用户不必翻阅完整个书就能迅速地找到所需要的信息。在数据库中，索引也允许数据库程序迅速地找到表中的数据，而不必扫描整个数据库。
2 B树的定义
2.1 B树的结构
本文删除记录时引起的结点内部数据变化，甚至整个结点内的记录都无效时，会调用刷新函数。该函数以树的根为参数，在遍历树时调用结点类的写入函数将新数据覆盖到数据库文件的原地址上。而有些被删除了的结点，在内存中的B树已经无法联系到，所以无法写入覆盖，也无需操作。所以实际上本系统的删除操作不会减少数据库文件的大小。
4 总结
本文描述了设计和实现了一种基于B树的小型数据库管理系统的过程。详细叙述了B树在本系统中的实现和应用，以及本系统如何构造了如常见数据库的表与字段，以及各个操作的流程。对B树性能进行分析计算。最终实验表明，B树非常适合作为存取辅助设备的数据结构。
参考文献
[1] Thomas H.Cormen， Charles E.Leiserson等著，潘金贵等译.算法导论（第2版） [M].北京：机械工业出版社，2006.9.
