（计算机应用技术专业论文）对多维数据存储技术的研究.pdf

武汉理工大学硕士学位论文 摘要 在目前激烈的市场竞争中，企业要想在竞争中立于不败之地，决策者必须 要做出快速、及时、准确的决策。这些决策的选择不再仅依据决策者的主观感 觉和经验，更主要来源于对企业过去业务数据的分析，他们需要对这些数据进 行不同角度的分析。根据对这些数据的分析结果，预测未来的商业趋势。若要 有效、高效的分析历史数据，就必须对其进行合理的组织与存储。 本文讨论了数据在磁盘中的存储以及组织结构，同时，为了提高查询分析 的效率，还要为数据文件建立多种索引；要对多维数据仓库中的多维数据进行 粒度的划分；对数据进行分割；对休眠数据进行处理等。粒度是数据仓库中数 据单位的细化或综合程度的级别，越详细的数据粒度越小。粒度越大，查询效 率越高，占用的存储空间少，但能完成的查询也就越少。数据分割是对数据仓 库中的细节数据进行分割，通常的分割标准有：按时间分割、按地理位置分割 等。数据量的大小是决定分割的主要因素。休眠数据管理是指对以后不用的数 据从要进行查询分析的数据仓库中剔除。这样可以在查询时减少扫描的次数从 而提高效率。 这里介绍了两种方法可以存储多维数据，一种是以二维关系表的形式存储， 一种是以多维数组的形式存储，分别对应r o l a p 与m o l a p 。关系表存储法也就是 用维表和事实表存储多维数据。用维表记录多维数据中的维度，用事实表记录 多维数据立方体各个维度的交点的度量值。由于在查询时要进行多个表之间的 连接，因而响应时间比较长，但对于有大量空白数据的数据库来说，可以节约 很多存储空间。多维数组存储法是直接处理存放在多维数组中的数据，这种数 据已经反映了各种数据的组合，并且每个单元都可以直接访问，一般而言，查 询速度比较快而且稳定。但在矩阵稀疏的情况下，会存在大量的数据空白点， 从而造成大量的空间浪费。针对m o l a p 中出现的空间浪费问题，我们要对其进 行压缩存储。可以通过增加一个冗余的标志位的方法记录某种组合是否有实际 可用的数据，在存储时只存储有数据的点，剔除空白点，达到压缩存储多维稀 疏矩阵的目的。 关键字：多维数据，数据仓库，o l a p 武汉理工大学硕士学位论文 a b s t r a c t i ft h ee n t e r p r i s ew a n t st ok e e pa ni m p r e g n a b l ep o s i t i o ni nt h ef i e r c ec o m p e t i t i o n o ft h em a r k e tn o w ，t h ed e c i s i o n - m a k e rm u s tm a k ef a s t , p r o m p ta n da c c u r a t ed e c i s i o n s t h i sd e c i s i o n - m a k i n gn ol o n g e ro n l yr e l i e so nd e c i s i o n - m a k e r ss u b j e c t i v es e n s a t i o n a n de x p e r i e n c eb u tt h ea n a l y s i so ft h ep a s tp r a c t i c a ld a t ao ft h ee n t e r p r i s e t h e d e c i s i o n - m a k e rn e e d st oc a r r yo nt h ea n a l y s i si nd i f f e r e n ta s p e c t s a c c o r d i n gt ot h e r e s u l t so ft h ed a t aa n a l y s i s , t h e yf o r e c a s tt h ec o m m e r c i a lt e n d e n c yi nf u t u r e i fw e w a n tt oh a v ea l le f f e c t i v ea n a l y s i so nt h e s eh i s t o r yd a t a , t h ed a t am u s tb em e m o r i z e d i nar e a s o n a b l e o r g a n i z e dw a y t h i sa r t i c l ed i s c u s s e st h ew a yi nm e m o r i z i n gt h ed a t aa n dt h eo r g a n i z a t i o n a l s t r u c t u r eo ft h ed a t ai nt h ed i s k s i m u l t a n e o u s l y ，i no r d e rt oi m p r o v et h ee f f i c i e n c yo f i n q u i r ya n da n a l y s i s ，w en e e dt oe s t a b l i s hd i f f e r e n tk i n d so fi n d i c e sf o rd a t af r i e s ， c a r r yo n t h e g r a n u l a r i t y d i v i s i o nt ot h em u l t i - d i m e n s i o n a ld a t a f r o m m u l t i - d i m e n s i o n a ld a t a b a s e ，t h ed a t ad i v i s i o na n dt h ed a t ap r o c e s s i n gt ot h ed o r m a n c y d a t aa n ds oo n t h eg r a n u l a r i t yi st h el e v e lo ft h es u b d i v i s i o no rt h es y n t h e s i sd e g r e e o fd a t au n i ti nt h ed a t a b a s e t h em o r em i n u t ed a t ah a sas m a l l e rg r a n u l a r i t y i ft h e g r a n u l a r i t yi sb i g g e r , t h ee f f i c i e n c yo fi n q u i r yw i l lb eh i g h e ra n dt h em e m o r ys p a c ei t t a k e sw i l lb es m a l l e r , b u tt h ei n q u i r i e si tc a nc o m p l e t ea r el e s s t h ed a t ad i v i s i o ni s c a r r i e do nt h ed i v i s i o na i m i n ga tt h ed e t a i ld a t ai nt h ed a t a b a s e t h eu s u a ld i v i s i o n s t a n d a r d sa r ct i m ed i v i s i o n , g e o g r a p h i c a lp o s i t i o nd i v i s i o na n ds oo n t h es i z eo ft h e d a t aq u a n t i t yi st h ep r i m a r yf a c t o ri nt h ed i v i s i o n t h ed o r m a n c yd a t am a n a g e m e n t r e f e r st ow e e d i n go u tt h ed a t af l r o mt h ed a t a b a s ew h i c ha r eu s e l e s st ot h ei n q u i r ya n d a n a l y s i si nf u t u r e i tc a ne n h a n c et h ee f f i c i e n c yb yr e d u c i n gt h es c a n n i n gt i m e s t h i sa r t i c l ei n t r o d u c e st w om e t h o d si nm e m o r i z i n gt h em u l t i - d i m e n s i o n a ld a t a o n eo ft h em e m o r i z i n gf o r m si st h et w o - d i m e n s i o n a lr e l a t i o n a lt a b l e t h eo t h e ri sb y t h em u l t i d i m e n s i o n a la r r a y t h e ya r cc o r r e s p o n d i n gw i t hr o l a pa n dm o l a p s e p a r a t e l y t h em e m o r i z i n g f o r mo ft h er e l a t i o n a lt a b l em e m o r i z e st h e m u l t i d i m e n s i o n a ld a t aw i t ht h ed i m e n s i o nt a b l ea n dt h ef a c tt a b l e w l l i l et h e d i m e n s i o nt a b l er e c o r d sm u l t i d i m e n s i o n a ld a t ai nd i m e n s i o n , t h ef a c tt a b l er e c o r d s 武汉理工大学硕士学位论文 m u l t i d i m e n s i o n a ld a t ac u b e sv a l u eo ft h ep o i n to fi n t e r s e c t i o ni ne a c hd i m e n s i o n b e c a u s et h ei n q u i r ym u s tc o n n e c tm a n yt a b l e s ，t h er e s p o n s et i m ei s l o n g b u t r e g a r d i n gt ot h ed a t a b a s ew h i c hh a st h em a s s i v eb l a n kd a t a , i tc a ns a v ep l e n t yo f m e m o r i z i n gs p a c e t h em e m o r i z i n gf o r mo ft h em u l t i - d i m e n s i o n a la r r a yp r o c e s s e s t h ed a t ai nt h em u l t i - d i m e n s i o n a la r r a yd i r e c t l y t h i sk i n do fd a t ah a sa l r e a d y r e f l e c t e da nk i n d so fd a t ac o m b i n a t i o n , a n de a c hu n i tc a nb ev i s i t e dd i r e c t l y g e n e r a l l ys p e a k i n g , t h ei n q u i r ys p e e di sq u i c ka n ds t a b l e b u tw h e nm a t r i xi ss p a r 鸵， t h e r ea mam a s so fd a t ab l a n k , t h u si tw a s t e sm a s s i v es p a c e k e y w o r d ：m u l t i d i m e n s i o n a l - d a t a ，d a t aw a r e h o u s e to l a p h i 独创性声明 本人声明，所呈交的论文是我个入在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特勇j 加以标注和致谢 豹地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料与我一同工作的同志对本研究所傲的任何贡献均已 在论文中作了明确的说明并表示了谢意。 关于论文使彤授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件允许论文被套阋和借阅： 学校可以公布论文的全部内容可以采用影印、缩印或其他复制 手段保存论文 保密的论文在解密后应遵守此规定) 研究生签名：塑丝盏导师签 武汉理工大学硕士学位论文 第1 章绪论 随着商业竞争激烈程度的加剧，企业如果要生存和发展，决策者必须要能 够做出及时准确的决策，而决策的依据不再仅仅是主观的经验与感觉，对企业 过去的业务数据分析也成了决策者做决定的重要依据。传统的数据库系统 联机事务处理系统( o u 甲) 作为数据管理的手段，主要用于商业操作中的事务 型处理，但它对分析型处理的支持一直不理想。从而人们便尝试对o l t p 的数 据库中的数据进行加工，形成一个面向分析的环境，以便更好的支持决策分析， 做出正确的决策【4 j 。o l a p 中分析的数据主要来源于o l t p 操作中的数据， o l t p 数据库中的数据经过过滤、提取等手段形成可用于分析的o l a p 数据。 1 2 课题研究的目的和意义 近年来，随着数据库应用的广泛普及，人们对数据处理的要求逐渐体现了 多层次的特点，对数据库的关注己不再仅仅是操作型处理，分析型处理作为决 策的依据越来越受到决策者的重视。商业经营者为了在市场竞争中立于不败之 地，就必须提高分析和决策的效率和有效性，而做出这些决策的依据恰恰是存 储在数据仓库中的大量的历史数据。在标准的编程语言中，多维数组的物理存 放方式通常是按照一种固定的顺序，按线性次序存放，不同维的访问效率差别 很大。就拿一个二维数组来说，如果按照行优先存放的话，则访问一个行中的 数组元素时，效率会很高，因为一次i ，o 读取的页面中可能包含了同一行的所 有数组元素，但访问一个列中的数组元素时，效率就会很差，在个别的情况下 每个页面仅包含该列中一个数组元素的值，需要多次y o 操作l 埘。另外，在数 据稀疏的情况下，由于大量数组元素没有需要存储的值，存储效率大大下降。 因此，如何组织这些数据的存储，以便有效的调用数据，提高时间、空间效率 日渐重要。 武汉理工大学硕士学位论文 1 3 和本课题有关的国内外研究现状 随着网络技术的推广和数理分析在银行业中的广泛应用，西方开始广泛采 用人口数理统计理论，运用数据挖掘及商业智能等技术，处理跨时间、跨空问、 跨部门、跨产品的银行数据集成分析问题，逐步实现了产品和服务的交叉销售。 目前，国内多家银行也不同程度地开展了商业智能系统建设1 2 1 。自1 9 7 0 年第一 个o l a p 的雏形工具e x p r e s s 发布，到1 9 9 3 年关系数据库之父、数学家与计算 机科学家爱德华库德( e f c o d d ) 系统地提出o l a p 概念和o l a p 的1 2 条准则， 0 l a p 技术和产品有了很大的发展，其内涵和外延也发生了很大的变化【1 1 】。但其 本质特征仍然是：以多维数据模型为基础组织和存储数据。m ma l m a d e n 研究中 心和微软进行了一个名为“q u e s t 的项目。研究重点是多维数据库的建模与组织。 威斯康辛大学和a t & t 的研究则侧重于实视图、o l a p 数据组织、数据立方体计 算等方面。虽然已经有论文和书籍给出了部分对多维数组有效地进行存储组织 的方法，但这些方法都还没有完全解决多维数组的高效存储过程中存在的一些 问题。首先，矩阵过于稀疏会导致大量的存储空间的浪费，而使用数据压缩技 术又会给o l a p 查询处理带来额外开销，因此需要选择有效的适合多维数组的 数据压缩方式。其次，多维数组初始建立后，当又有数据需要进入时，对于现 在的多维数组存储方式一般都需要重构多维数组，并且随着数组的膨胀，重构 的开销也越来越大。另外，现在的多维数组结构都没有考虑如何有效地存储维 内部的层次信息( 关系存储方式通过使用雪花模式来处理维内部的层次问题) 。 1 4 研究的目标及内容 本文针对当前多维数组存储组织方式存在的一些问题，提出了一种改进的 多维存储结构。在设计过程中，我们充分考虑了实际多维数组的大容量和高稀 疏度等问题，提出了一种多维数组的压缩存储技术，使得基于该多维存储结构 能够优化处理各种o l a p 查询( 区域查询，聚集查询等) ，特别是通过在多维存储 结构中存储各维内部的层次信息，提高涉及维内部层次的查询的响应速度并实 现对多维数据的调用。 2 武汉理工大学硕士学位论文 第2 章物理存储结构 数据库管理系统的数据操作算法、查询优化算法和事务处理算法与数据库 的物理存储结构密切相关。在考虑物理存储结构时，我们不再关心应用程序如 何看待数据，而主要考虑如何在外存储器上以最优的方式存放数据。物理结构 设计主要考虑数据库的操作效率、响应时间和空间利用率。 2 1 数据库的存储设备 数据库通常存储在辅助设备上，目前主要使用的存储设备是磁盘存储器存 储器。一些新的辅助存储器也正在出现，但这些新的存储器目前还很少使用到 数据库系统。 2 1 1 磁盘存储器 磁盘是用磁性材料制成的圆盘，数据存储在磁盘表面。磁盘可分为单面磁 盘和双面磁盘。为了增加磁盘的容量，人们把多个磁盘组装在一起，形成一个 磁盘组。一个磁盘组可以具有数十个存储数据的磁盘表面。每个磁盘表面由多 个磁道组成，数据存储在磁道上，每个磁道表面可以分为多个扇区，在磁盘组 上，所有磁盘表面上具有相同直径的磁道集合称为一个柱面l q 。 磁盘存储器的读写单位是扇区，每个扇区可以存储许多个字节的信息。主 存储器与磁盘存储器交换信息必须以磁盘块为单位。磁盘存储器是一种随机存 储器。我们可以随机读取任何一个磁盘块，磁盘地址形式如表2 1 所示： 表2 一l 磁盘地址 在进行磁盘读写时，主存储器必须具有与磁盘存储器磁盘块容量匹配的缓冲区， 用来存储磁盘块的数据。 3 武汉理工大学硕士学位论文 2 1 2 磁盘容错技术 磁盘会由于多种原因出现故障，当磁盘发生故障时，如果数据没有备份到 另一种介质中，数据将会永久的丢失，这种情况对于重要的d b m s 应用来说是 一种灾难。目前，人们已经提出很多减少磁盘故障引起数据永久性丢失的策略。 它们通常都涉及磁盘冗余技术，这些方法都使用一个或多个磁盘保存数据。使 用附加的一个或多个磁盘保存与数据磁盘内容相关的信息。当数据磁盘发生故 障时，附加磁盘的信息可以用来实现故障磁盘的恢复。当附加磁盘发生故障时， 数据磁盘的数据或其他磁盘的冗余信息可以用来实现故障磁盘的恢复，基于磁 盘冗余技术的策略通常被称为r a i d 策略，下面讨论几种r a i d 策略。 2 1 2 1 简单r a m 策略 简单r a i d 策略也称为r a i d l 策略，其基本思想是为每个数据磁盘增加一 个冗余磁盘( 也称为镜像磁盘) 。在正常运行中，冗余磁盘中的数据与对应的数 据磁盘中的数据保持一致，当数据磁盘发生故障时，冗余磁盘代替其工作，当 数据磁盘故障修复或新的数据磁盘加入系统后，冗余磁盘中的数据被复制到数 据磁盘，使系统恢复正常运行。如果冗余磁盘与数据磁盘同时发生故障，简单 r a i d 策略将失败。如果数据磁盘( 或冗余磁盘) 进行恢复时，冗余磁盘( 或数 据磁盘) 又出现故障，简单r a i d 策略也将失败。 简单r a i d 策略是减少磁盘故障保证数据完整的有效方法，但简单r a i d 策 略要求使用的冗余磁盘数量与数据磁盘数量一样多，这样，就会有许多磁盘被 浪费，为了解决这个问题，人们提出了基于奇偶校验的r a i d 策略。具有奇偶校 验的策略有r a i d 2 、r a i d 3 、r a i d 4 、r a i d 5 、r a i d 6 策略，这里仅讨论常用 的几种。 2 1 2 2r a i i m 策略 不管一个系统具有多少个数据磁盘，r a i d 4 策略都只使用一个冗余磁盘。 假设系统具有n 个相同数据磁盘，编号为1 ，2 ，3 n 。r a i d 4 策略仅使用一 个冗余磁盘完成对n 个数据磁盘的奇偶校验。冗余磁盘的第i 块存储所有的n 个 数据磁盘第i 块的奇偶校验位，也就是说，如果所有n 个数据磁盘的第i 块第j 位上的1 的个数是偶数，则冗余磁盘第i 块第i 位为0 ，否则为1 。 例如，假设系统具有三个相同的数据磁盘( 我们命名为：盘1 ，盘2 ，盘3 ) ， 4 武汉理工大学硕士学位论文 和一个冗余盘( 盘4 ) ，每个磁盘块存储8 位的数据，如果3 个数据磁盘的第i 块存储如下数据： 磁盘1 ： 1 1 1 1 0 0 0 0 磁盘2 ：1 0 1 0 1 0 1 0 磁盘3 - 0 0 1 1 1 0 0 0 则冗余磁盘4 中第i 块必须存储的数据为：0 1 1 0 0 0 1 0 。 这样，若系统具有n 个数据磁盘和一个冗余磁盘，则可以通过读这n + 1 个 磁盘中的任何1 1 个磁盘数据而推导出另一个磁盘的数据。同时，如果我们正在 读数据磁盘1 中的数据块，而这时存在一个请求也读磁盘1 中的数据，如果其 余磁盘都处于空闲状态，我们可以不必等待第一个请求完成，可以通过读其他 磁盘中的数据得到磁盘1 中的数据。 现在来考虑一下r a i d 4 策略如何保证磁盘发生故障时数据不丢失。假设系 统中有一个磁盘发生了故障，我们只需换上一个新的磁盘，根据奇偶校验原理 恢复它的数据，还以上一个例子为例，假设磁盘2 发生了故障，且看如何恢复 磁盘2 的数据。首先读出磁盘1 、3 、4 中的数据，之后根据奇偶校验原理导出 丢失的数据块的数据是1 0 1 0 1 0 1 0 。 2 1 2 3r a i d 5 策略 r a i d 4 策略存在一个瓶颈问题，即无论更新哪一个磁盘中的数据，都要对 冗余磁盘进行写操作，为此人们提出了r a i d 5 策略。 从上面的介绍可以看出，数据恢复规则对数据磁盘和冗余磁盘是相同的， 即，其他磁盘相应位的模2 和是被恢复磁盘相应位的值。于是，我们没有必要 一定把某一个磁盘作为冗余磁盘，把其他磁盘作为数据磁盘。我们可以把每个 磁盘都作为其他磁盘相应磁盘块上的冗余磁盘。这样在写某些数据磁盘时，可 以使对冗余磁盘的写操作分布到每个磁盘中，并发写冗余磁盘，解决了r a i d 4 策略的瓶颈问题。 2 2 文件和文件记录 数据通常都是以记录的形式存储在磁盘上，记录由一组相关的数据值或数 据项组合而成，每个数据项对应记录的一个域，它由一个或多个字节组成，记 5 武汉理工大学硕士学位论文 录的每个域有一个名字和一个数据类型。一组域名和它对应的数据类型构成了 记录格式。文件是一个记录序列，如果一个文件所有记录都有相同的长度，称 这个文件为定长记录文件，若记录长度不一致，则称该文件为变长记录文件。 由于主存储器与磁盘存储器之间数据传输单位是磁盘块，所以，磁盘文件 记录必须划分成多个大小与磁盘块容量相同的块，每一块称为一个文件块。每 个磁盘块存储一个文件块。当磁盘容量大于记录长度时，每个文件块可以包含 多个记录，若记录长度大于磁盘块容量，则记录必须被划分成多个文件块。这 时，每个磁盘块需要存储一个指针，它指向下一个存储相同记录数据的磁盘块。 在磁盘上存储记录的方法很多，这里介绍几种常用的方法，第一种方法称 为连续存储法。该方法按照文件中文件块的顺序把文件存储到连续的磁盘块上。 使用这种存储方法存取整个文件的效率较高，但添加新的数据困难。第二种方 法是链接存储方法，这种方法在每个文件块中增加一个指向下一个文件块地址 的指针。这种方法便于文件扩充，但读取整个文件的速度较慢。第三种方法称 为索引存储法，这种方法在磁盘上存储一个或多个索引块，每个块包含指向下 一级索引文件或数据文件块的指针。 2 3 无序文件 无序文件是一种最简单的文件，记录被随机的存储在文件中，新的记录存 储在文件末尾，也被称为堆文件。无序文件既可以存储定长记录也可以存储变 长记录。无序文件查找效率低，要查找一个满足条件的记录，必须从文件的第 一个记录开始搜索，直到发现满足条件的记录。如果满足条件的记录不止一个。 还必须搜索整个文件。 2 4 有序文件 在有序文件中，记录按照某个( 或某些) 域的值的大小顺序排列。用于排 序的域称为排序域。如果有序文件上的查找定义在排序域上，则可以使用二分 查找法非常有效的找到满足条件的记录。时间复杂度为l o n 。对于查询条件定 义在非排序域上的查找操作来说，排序文件没有任何优越性。有序文件插入和 删除操作比较复杂，需要保持文件的有序性。因此，耗费的时间较大，当插入 6 武汉理工大学硕士学位论文 一个记录时，必须首先确定这个记录的插入位置，然后移动文件记录为被插入 的记录准备存储空间，最后插入记录。对于删除记录，我们可以使用删除标志 位和定期清理存储空间实现删除操作，这样，消耗的时间相对插入操作要少。 2 5 h a s h 文件 h a s h 文件是一种支持快速存取的文件存储方法，如果用h a s h 方法存储一个 文件，首先需要指定文件的一个或一组域为h a s h 域，然后定义一个在h a s h 域 上的函数，称该函数为h a s h 函数。设f 是一个文件，a a 是f 的h a s h 域，h a 是定义在a a 的值域上的函数，如果f 的记录r 的a a 域值为a ，则r 的存储地 址由h a ( a ) 决定。在h a s h 文件中，记录r 的地址一般不是记录的存储地址，而 是r 所在的磁盘块的地址，若要查找h a s h 文件的记录。首先，使用h a s h 函数 找到记录所在的磁盘块，读入主存缓冲区，然后在缓冲区中顺序查找记录【“。 2 5 1 简单h a s h 方法 简单h a s h 方法把文件划分为n 个h a s h 桶，每个h a s h 桶对应一个磁盘块。 每个h a s h 桶有一个编号，为了实现h a s h 桶编号到磁盘块地址的映射，每个h a s h 文件具有一个h a s h 桶目录，第l 号h a s h 桶目录项中存储该h a s h 桶对应的磁盘 块指针。图2 1 给出了h a s h 桶目录示例，当n 不大时，h a s h 桶目录可以保存 在主存中，否则存储在磁盘上。 桶编号 磁盘块地卅( 二 0 j 1 广 广 1 7 t 亡= 亡= n厂( 二 h a s h 桶目录磁盘块集合 图2 - 1h a s h 桶目录 h a s h 函数把文件h a s h 域的每个值映射到一个h a s h 桶上。很明显，每个h a s h 7 武汉理工大学硕士学位论文 桶对应的磁盘块存储具有相同h a s h 函数值的记录。 如果文件数据在h a s h 函数属性上分布不均匀，可能产生桶溢出问题，也就 是说具有相同h a s h 函数值的记录数超过了磁盘块所能容纳的记录数。处理溢出 通常用以下几种方法： 1 、多重h a s h 方法，设计溢出处理h a s h 函数，用它来确定溢出记录的存储 地址。 2 、链接法，对于每个桶设置一个磁盘块链表，链表的第一个磁盘块存储正 常记录，其他磁盘块存储溢出记录。 链表法是使用最多的处理溢出的方法，通常称链表方法处理溢出问题的 。h a s h 方法为链接h a s h 方法，图2 _ 一2 给出了链接方法的示意图： 桶编号磁珊i # f f h n - 0 1 n h a s h 桶目录磁盘块地址 图2 2h a s h 桶目录链接方法的示意图 在h a s h 表上的查找操作需要分两种情况处理，如果h a s h 文件上的查找操 作具有如“a _ a ，的查询条件，其中a 为h a s h 域，a 是常数，可以按如下方法查 找满足条件的记录：首先计算h c a ) ，得到桶的编号i ，然后查找桶的目录找到桶 的磁盘链上的第一个磁盘块地址，并顺着链扫描检查每一块，直至找到满足条 件的记录或确定没有满足条件的记录为止。如果查找条件“a _ a ”的a 不是h a s h 域，则需要使用无序文件上的查找方法来处理这个查找操作。 h a s h 文件的插入操作过程如下：首先使用h a s h 函数计算出插入记录的桶号 i ，然后在桶i 的磁盘块链上寻找空闲空间，若找到则将记录存入。若链上所有 块上无空闲空间，向系统申请一个磁盘块，将记录插入，并将新块链入磁盘块 链。 h a s h 文件上的删除操作分两种情况处理：如果已知要被删除的记录的h a s h 8 武汉理工大学硕士学位论文 域的值，则使用h a s h 函数计算出欲删除的桶的编号l ，在桶l 的磁盘块链上找到 欲删除的记录，将其删除。若删除记录后磁盘块为空，则释放该磁盘块修改磁 盘链。如果不知道欲删除记录的h a s h 域值，则需要使用无序文件上记录删除方 法执行删除操作。 h a s h 文件上的修改操作需要分两种情况处理，当要修改记录的h a s h 域的值 时，用一个删除和插入操作来代替完成。如果欲修改非h a s h 域的值，则调用查 找操作，找到欲修改记录的磁盘块，读入主存缓冲区，在缓冲区中修改记录， 之后写回磁盘。 简单的h a s h 方法是一种快速查找的方法，但同时还具有以下缺点： 1 、只能有效的支持在h a s h 域上具有相等比较的数据操作，如果一个数据 操作不是建立在h a s h 上或不是相等比较，则数据操作时间与无序文件相同。 2 、由于h a s h 桶的数量一成不变，当文件记录较少时，将浪费大量的存储 空间，当文件记录超过一定数量以后磁盘块将会很长，影响记录的存取效率。 2 5 2 动态h a s h 方法 在动态h a s h 方法中，h a s h 桶号与磁盘块一一对应，h a s h 桶的数量不是固 定不变的，而是随着文件记录的变化而变化。初始时，h a s h 文件只有一个h a s h 桶，当记录增加到使这个桶溢出时，它被分割成两个h a s h 桶，原h a s h 桶中的 记录也被划分为两部分，h a s h 桶值为1 的记录分割到第一个h a s h 桶，h a s h 值 为0 的记录被划分到另一个桶中，当h a s h 桶再次溢出时h a s h 桶又被划分成两 部分。同样，当相邻h a s h 桶中的记录数不超过一个磁盘块所能容纳的记录数时， 可以把两个桶合并为一个桶。动态h a s h 法需要一个用二叉树表示的目录，二叉 树目录的级数随h a s h 桶的分裂和合并增加或减少。如果h a s h 函数能够把记录 均匀的分布到各个h a s h 桶中，二叉树目录将是一个平衡二叉树。 2 6 索引文件 文件的索引通常定义在一个或多个域上，这组域称为索引域，索引也是一 个文件，称为索引文件。相应的，被建立索引的文件被称为数据文件，索引文 件的记录称为索引记录或索引项。每一个索引记录包括两个域，第一个域用来 存储索引域的值，第二个域用来存储一个或一组指针，每个指针指向一个索引 9 武汉理工大学硕士学位论文 域对应的记录所在的磁盘块的地址【1 s l 。索引文件通常按索引域的值的大小来捧 序，为提高存取效率和节省存储空间，索引文件一般都远小于数据文件，按照 索引域的特点，索引可以分为主索引、聚集索引和辅助索引 2 6 1主索弓l 主索引是一个具有两个域的有序定长文件，主索引文件记录的第一个域的 数据类型与数据文件的键的数据类型相同，存储索引域的值。主索引文件记录 的第二个域是指针域，存储指向磁盘块的地址，索引文件中每个索引记录对应 一个磁盘块，第一个域存储磁盘块中第一个数据记录的索引域值，第二个域存 储指向这个磁盘块地址1 1 2 1 。很明显，主索引是一个稀疏索引，图 - 3 给出了一 个主索引文件例子。 索引域磁盘块地址 一如 c h a r t d 呻id u t a n t a n 索引文件数据文件 图2 3 主索引文件示例 由于索引文件的记录数远比数据文件的记录数少，并且每个索引文件记录 的长度也远小于数据文件记录的长度，所以索引文件比数据文件小的多。于是， 检索索引文件比直接检索数据文件可以节省大量的检索时间。主索引与有序文 件存在相同的问题，即在处理数据的插入、删除和修改操作时需要维护数据文 件和索引文件记录之问的对应关系。 2 6 2 聚集索引 如果一个有序文件的排序域是一个非键域，文件的不同记录在这个域上可 能有相同的值，我们称这个排序域为聚集域。我们可以在聚集域上为一个有序 文件建立一个索引，这种索引被称为聚集索引。聚集索引不同于主索引之处在 武汉理工大学硕士学位论文 于它不要求每个索引域的值仅对应唯一的一个记录 聚集索引文件也是一个有序文件，每个索引记录有两个域，第一个域也是 数据类型，它同数据文件的数据类型相同。第二个域是指向磁盘块的指针。聚 集索引是稀疏索引，与主索引存在相同的问题，数据的维护工作比较复杂。也 需要维护数据文件和索引文件记录之间的对应关系。 2 6 3 辅助索引 辅助索引是建立在数据文件的非捧序字段上的索引，即索引域是数据文件 的非捧序域，与其他索引文件一样，辅助索引文件也是有序文件，每个索引记 录同样有两个域，第一个域存储数据，其中的数据类型与数据文件相同。第二 个域存储指向磁盘块地址的指针。一个文件上可以建立多个辅助索引，因此， 可以有多个辅助索引域。 2 6 4 多级索引 索引是提高存储访问效率的基本方法，但是如果索引文件本身很大，索引 的查找代价也会很大，那么很自然的会想到为索引文件再建立索引，这个过程 可以一直持续下去，直到满足要求为止。这就是多级索引的思想。在多级索引 中，各级索引文件本身都是在索引域上的有序文件，而且索引域是索引文件的 键域，所以，在多级索引文件中，除了第一级索引文件以外，每级索引都是前 一级索引文件的主索引，图2 - - 4 给出了一个二级索引文件的示例。 叫2 7 2r i 4 ol- i8 l ：lr i - s | 3 5 | 一兰i 目| | 9 1 图2 4 二级索引文件的示例 1 1 武汉理工大学硕士学位论文 多级索引文件的插入、删除和修改记录操作更加复杂，需要维护多级索弓 文件的有序关系，从而使维护工作变得困难。 2 7树索引结构 2 7 1b 树索引结构 b 树是具有附加限制的索引树，附加条件是为了保证索引树的平衡，减少磁 盘存储空间的浪费和查询的时间闭。为了保证这些条件成立，具有b 树索引文 件的插入和删除操作十分复杂。 b 树的定义：一个秩为d 的b 树索引结构是一个满足下列条件的树型数据 结构： ( 1 ) 每个内节点存储有信息( t p l ， ，t p 2 , ， j r p q ) ，其中，q 小于或等于d ，t p i 是树指针，它指向下一个子节点；d p i 是数据指针，指向一个包含索引域值为k 的数据文件记录的磁盘块地址。 ( 2 ) 在t p i 指向的子树中，每个索引域的值x 都满足：对于1 i q - 1 ，1 c x k 0 对于i 1 ，x 满足x l 【a 1 0 ( 3 ) 每个节点至多有d 个树指针。 ( 4 ) 如果根节点不是树的唯一节点，那么它至少有两个树指针。 ( 5 ) 具有q 个树指针的节点有q - 1 个索引域值，进而有q - 1 个数据指针。 ( 6 ) 所有叶节点在树的同一级。叶节点结构与内节点结构相同。只是树 指针为空。 图2 _ _ 5 给出了一个简单b 树结构。 图2 - - 5 简单b 树结构图 武汉理工大学硕士学位论文 在上面的论述中，如果b 树的索引域是数据文件的键域，则每个索引值仅 对应一个数据指针。b 树索引也可以定义在数据文件的非键域上，即b 树的索 引域不是数据文件的键域。此时，必须改变数据指针d p i 的定义。d p j 不再直接 指向数据文件的一个磁盘块，而是指向一个磁盘块链表，这个链表存储所有指 向索引域值为l 【i 的数据记录所在磁盘块地址的指针记录。 下面给出b 树的查找算法： p = 根节点的磁盘块地址； w h i l ep 不是空指针) 读取p 指向的节点到主存缓冲区； i f ( 存在一个i 使l ( i = k ) 读由d p i 确定的数据文件到主存缓冲区b u f f ，在b u f f 中 找出索引键为k 的记录； r c t u r n ( 找到的记录) ； e l s e i fk k i p = t p q ； i f 存在一个l 使得k l 和n o d e 的所 有信息分为两半，按次序分放在两个磁盘块中。我们称这个过程为分裂。分裂 后将中间的检索值k 对应的 升到n o d e 的父节点中，如果父节点也满， 则要再次进行分裂。如果这种过程一直持续到根节点，那么此时的树就会增加 一层。 对于删除操作，我们拿一个例子来说明。如果要把r 删除，首先在b 树上 武汉理工大学硕士学位论文 找到 ，把r 从磁盘块中删除，然后分为两种情况删除 ：( 1 ) 如果 c k d p 在叶子节点中，则找到指定的叶子节点n o d e ，把( 1 【，d p 从n o d e 中删除； ( 2 ) 如果 在非叶节点中，则找到相应的节点n o d e ，把 删除，并 在b 树中找到一个大于k 的最小k 所对应的( k ，d p 也就是n o d e 中 右 边的树指针所指向的子树的最左叶子节点 ，把 移到n o d e 中 的位置。 在上述两种情况下，均要检索叶节点n o d e 的索引域值个数是否小于d 2 。 如果小于，则把相邻兄弟节点中一些“t p ”或“ t p ”移到这个 修改过的叶子节点，使两个节点的索引域个数相等，而且都不小于d 2 。如果相 邻兄弟节点的关键字个数正好是d 忪，则把n o d e 与这个兄弟节点和二为一。这 样，n o d e 的父节点中少了一个“t p ”或“ t p ”，因而又可能与其 他节点合并，此过程也可能一直持续到根节点。 2 7 2b + 树索引结构 b + 树是对b 树的改进，在b + 树中，数据指针只能出现在叶子节点而不是象 在b 树中那样可一出现在树的任何一级。于是，b + 树的叶节点结构与内部节点 结构不同，对于每个索引域值，叶节点中都有一个对应的索引项。叶子节点中 的索引项由两个域组成，一个域是索引值域，一个域是指针域。如果索引值域 存储的值为v ，若索引域是数据文件的键，则指针域存储一个指向包含索引域值 为v 的数据记录的磁盘块的地址，如果索引域不是数据文件的键域，那么索引 值为v 的记录不唯一，它是一个记录的集合，设为s 。这时，指针域存储指向 一个磁盘块a 的指针，a 中存储s 个指针，每个指针指向一个包含s 的记录的 磁盘块的地址，相当于增加了一级索引，另外，b + 树的叶子节点链按在一起。 一个b + 树的内节点定义如下： ( 1 ) 每个内节点具有形式 ( 2 ) 在树指针p i 指向的子树中，每个索引域的值x 满足：对于l 【i q - 1 ，& 1 x = x l ；对于i = 1 x k o l 。 ( 3 ) 每个节点最多有d 个树指针 ( 4 ) 除根节点和叶子节点外，每个节点至少有d 2 个树指针，如果根节点 不是树的唯一节点，它应该至少有两个树指针。 ( 5 ) 具有q 个树指针的节点有q - 1 个索引域值。 1 4 武汉理工大学硕士学位论文 b + 树的内节点如图2 - - 6 所示： 耳i 找= k t 图扣喝b + 树的内节点 一个秩为d 的b + 树的叶节点定义如下： ( 1 ) 叶节点的形式为 ，其 中q 不大于d ，d p i 是数据指针，指向包含索引域值为k 的数据记 录的磁盘块，p n e x t 是指向b + 树下一个叶子节点指针。 ( 2 ) 所有叶节点至多有d 个数据指针，至少有d 2 个数据指针。 ( 3 ) 所有叶子节点都在同一级上。 b + 树的叶节点如图2 - _ 7 所示： 数据指针下一个叶子节点 图2 7b + 树的叶节点 b + 树的查找、插入和删除过程与类似于b 树。 武汉理工大学硕士学位论文 2 8 多维索引 到现在为止，我们都隐含地假设只使用一个索引来执行关系上的查询，但 对于某些类型的查询来说，如果存在多个索引，则使用多个索引会有更另人满 意的结果。 假设某银行账户表a c c o u n t 文件有两个索引，分别建立在b r a n c h - n a m e 和 b a l a n c e 上，考虑如下查询“找出c h i n a 支行中余额等于1 0 0 0 元的账号”我们有如 下查询语句s e l e c tl o a n - n u m b e rf r o ma c c o u n tw h e r