内存数据库的数据结构分析

tom_111 · 发表于 2007-12-5 10:01

摘　要：数据库管理系统获得高性能的一个方法就是将数据库存放在内存中而不是存放在磁盘上，这样就必须设计出一种新的数据结构和算法来更有效地利用CPU周期和内存空间。本文介绍了几种适合于内存数据库的物理数据组织方法和当前内存数据库管理系统的几种索引结构。
关键词：内存数据库；影子内存；T树；物理数据
Analysis of Data Structure in Main Memory DataBase
　　WANG Honghai，PAN Zhaohua
　　（College of Communication Engineering，PLA University of Science＆Technology，Nanjing，210007，China）

　　Abstract：To store database in main memory rather than on disk is a approach to achieving high performance of database　management system．So new data structures and algorithms must be designed．This article introduces several data organizing　 methods and index structures for main memory database．
　　Keywords: main memory database; shadow memory; T-tree; physics-data
按照目前内存芯片密度每年2倍的增长速度，在未来10年中，配置1 G或更大的内存将是很平常的事。内存容量的快速增长对数据库管理系统有着深刻的影响。在某些场合，将整个数据库放进内存是可能的，正常的查询处理可以完全脱离硬盘。另外，和传统的数据库应用相比，有大量的新兴应用，目前的内存大小已经足够了。
　　在数据库系统中，有2种方法来使用大量的内存。
　　（1）增大缓冲池　将一个事务所涉及的数据都放在缓冲池中。当采取这种方法的时候，算法优化的目标仍然是最小化磁盘访问。
　　（2）常驻内存数据库　将整个数据库放进内存中。这种方法需要重新设计一种数据库管理系统，需要对查询处理、并发控制与恢复的算法和数据结构进行重新设计，以更有效地使用CPU周期和内存。

1　磁盘和内存
　　内存数据库的索引结构和基于磁盘系统的索引结构不同，面向磁盘的索引结构的目标是最小化磁盘访问次数和空间占用，而面向内存的索引结构全部放在内存中，因此没有磁盘访问次数的最小化。这样，内存索引的目标是减少整体的计算时间同时尽可能少地占用内存。由于关系常驻内存，在索引中没有必要存储真实的属性值，而存储指向元组的指针，当需要的时候通过这些指针能够得到属性值。这样做有4个优点：
　　（1）单一元组指针便能访问元组的属性和元组本身，这就减少了索引的大小。
　　（2）避免了处理在索引中的长字段、可变长字段以及压缩技术。
　　（3）当更新索引操作时，移动指针将比移动属性值更廉价。
　　（4）由于单个元组指针提供访问这个元组中的任何字段，采用一种特殊的机制多属性索引的需要将减少。

tom_111 · 发表于 2007-12-5 10:02

2　物理组织方法
　　内存数据库的总体设计目标是使内存和CPU的利用率尽可能高，而内存数据库的物理组织是实现该目标的基础，其存储结构、索引结构、中间数据存储结构都必须考虑内存的直接存取这一特征，这里介绍几种适合于内存数据库的物理组织方法。
2.1　区-段式
　　区-段式组织是基于关系数据模型的。他将存储空间逻辑划分为“分区”，每一个分区存储一个关系。由若干“段”组成，一个段是内存中固定长度的连续区域，相当于“页”，但比页大，是内外存I／O的单位，也是内存空间分配以及内存数据库恢复的单位，区段式数据组织管理机制如图1所示。

tom_111 · 发表于 2007-12-5 10:03

一个段中的一个数据记录就是一个关系元组。每个记录有一个惟一的标识符RID（Record Identifier），他是一个三元组＜P，S，L＞，其中P，S，L分别为分区号、段号、段内的记录槽号，记录槽（RecordSlots）包含了对应记录的长度和记录的首地址。这样由RID经分区表和相对应的段表找到相对应的记录槽，按槽中的地址和长度便可直接存取所要的记录。其实，对于内存数据库，存取方法返回的不必是所需的记录数据的副本，只需将其槽中的地址返回即可。

2．2　影子内存式
　　按影子内存式组织的内存数据库空间可以划分为2部分：一部分是MMDB的主拷贝；另一部分为“影子拷贝”。影子内存式MMDB的体系结构如图2所示。

tom_111 · 发表于 2007-12-5 10:03

在事务的正常操作期间，每次查询都产生一个分别对于影子内存SM（ShadowMemory）和主拷贝PDB（Primary DataBase）的双地址，且总是先对SM试探，若不成功，再对PDB操作。所有的更新操作都在SM中进行，且都记录在活动日志中（Active Log）。每当一个事务提交时，由他所产生的在SM中的“后映像”拷贝到PDB中。使用影子内存的优点是：
　　（1）减少了日志缓冲区，因为其后映像区和用户区合二为一。
　　（2）省去因事务失败或系统故障时的UNDO操作，只清除相应的影子内存即可。
　　（3）减少对MMDB（PDB）存取，各事务可并行对各SM区操作。
　　（4）缩短恢复过程，这是因为一方面如（2）所述，省去UNDO型操作，只需做REDO型操作；另一方面还可以就当前事务对SM做“部分恢复”以后，就先启动正常事务处理，然后按需要逐步恢复PDB。
　　影子内存式和区-段式可以组合使用。
2．3　索引的组织方式
　　对于快速查询数据，索引是必须的。内存数据库的索引中并不存储真实的属性值，而存储指向元组的指针，当需要的时候通过这些指针能够得到属性值。很多数据结构可以作为索引的数据结构。下面简单描述每个算法的特点。
　　数组被用来作为索引结构的优点是他占用的空间最少，而且结构简单，查询速度快。数组最大的缺点就是每次更新时数据移动是O（n）的，因此他在一个动态的环境下是不实用的，但是如果在一个相对静态的环境下，数组是一个不错的选择。
　　AT＆TBell实验室Silicon数据库核心组织用AVL树作为索引结构。AVL树被设计为内部存储的数据结构，他是一个二*树，他的检索速度是很快的，这是因为二分检索是树结构的一个本质特性。更新总是影响叶节点可能导致不平衡，因此树必须通过旋转操作来保持平衡。AVL树最大的缺点是他的存储利用率太低。每个树节点仅仅有一个数据项，有2个指针和每个数据项的控制信息。
　　B树是比较合适用于磁盘的数据结构，由于他是一个宽而浅的树，查找一个数需要访问很少的节点。大部分数据库系统用一个B树的变种B＋树，他保存所有的数据在树的叶节点上。然而，对于内存数据库，B树比B＋树更合适，因为在内存中保存所有的数据在叶子上并非优点，他太浪费空间。B树的内存利用率是比较好的，所以他用于内存数据库比较合适；搜索速度比较快（用二分查找时，只访问很少一部分节点）；而且更新速度也比较快（数据移动通常只涉及到一个节点）。
　　链接的桶Hashing用于磁盘和内存中的静态结构。他非常快因为他是静态结构—不需要重新组织数据。但是，这种优点同时也是他的缺点：因为他是静态的，在一个动态的环境中他几乎不能工作，在填Hash表之前，他的大小必须是已知或可以猜得到的。如果估计的值太小，性能将是很差的，如果估计的值太大，将会浪费很多空间。最好的情况也有一些空间被浪费，因为每个数据项都有一个指针和他相联系。
　　可扩展Hashing使用了动态的Hash表，因此表的大小事先不用知道。一个Hash节点可容纳几个数据项，而且当溢出发生时可以分裂成2个节点。目录以2的指数倍增长，只要一个节点溢出而且目录已经达到了指定的最大目录深度，他就会加倍。可扩展Hhashing的一个问题就是任何一个节点都能引起目录分裂，因此如果Hash函数不是很随机的话，目录可能增长的很大。

tom_111 · 发表于 2007-12-5 10:04

线性Hashing也用一个动态的Hash表，但是他与可扩展Hashing有很大不同。和可扩展Hashing相比，当线性Hashing的一个节点分裂的时候，Hash表以预先定义好的线性顺序线性增长。以一种可控制的方式分裂一个节点和扩展目录比可扩展Hashing那种没有控制的分裂要有几个优点：
　　（1）桶是顺序排列的，桶的地址可以通过一个基地址计算出来，目录不必要。
　　（2）触发一个节点分裂的事件是基于存储空间的利用，这样对一些给定的元素，可以保持存储花费不变。
　　改进的线性Hashing比上面介绍的几种更适合于内存。通过用较大的相邻的节点而不是用一个目录，普通的线性Hashing有空节点（当一个节点对应的Hash入口没有数据项的时候）因而浪费空间，除非有一种聪明策略：用底层的虚拟内存映射机制计算出那些当目录增长时不得不拷贝到一个较大内存块的连续节点。改进的线性Hashing用一个很像可扩展Hashing的目录，但是他是线性增长的，而且每个节点只有一条数据，共同从一个内存池里分配内存。分裂的标准是基于性能而不是存储利用率，例如Hash链的平均长度。监视Hash链的平均长度比监视存储利用率在平均搜索花费和更新次数上提供了更直接的控制。
　　T树，一种新的数据结构，他是由AVL树和B树发展而来的。T树是在一个节点有很多元素的二*树，如图3所示，T树的一个节点叫做T节点如图4所示。由于T树是二*树，他保持了AVL树的内在的二分搜索的特征，而且，因为T节点包含了很多元素，T树有比较良好的更新和存储特性。对于插入和删除需要数据移动，通常只需要在单个节点内。用类似AVL树的旋转来重新平衡T树，但是他比AVL树次数要少，因为他存在数据移动在一个节点内部的可能性。现在，大部分内存数据库系统都采用T树作为其索引结构。