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

《内存数据库的数据结构分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、第1内容加载中...　　MDB的主拷贝；另一部分为“影子拷贝”。影子内存式MMDB的体系结构如图2所示。　　500)this.style.ouseg(this)">　　在事务的正常操作期间，每次查询都产生一个分别对于影子内存SM（Shadoory）和主拷贝PDB（PrimaryDataBase）的双地址，且总是先对SM试探，若不成功，再对PDB操作。所有的更新操作都在SM中进行，且都记录在活动日志中（ActiveLog）。每当一个事务提交时，由他所产生的在SM中的“后映像”拷贝到PDB中。使用影子内存的优点是：　　（1）减少了日志缓冲区

3、，因为其后映像区和用户区合二为一。　　（2）省去因事务失败或系统故障时的UNDO操作，只清除相应的影子内存即可。　　（3）减少对MMDB（PDB）存取，各事务可并行对各SM区操作。　　（4）缩短恢复过程，这是因为一方面如（2）所述，省去UNDO型操作，只需做REDO型操作；另一方面还可以就当前事务对SM做“部分恢复”以后，就先启动正常事务处理，然后按需要逐步恢复PDB。　　影子内存式和区-段式可以组合使用。2．3　索引的组织方式　　对于快速查询数据，索引是必须的。内存数据库的索引中并不存储真实的属性值，而存储指向元组的指针，当需要的时候通过这些指针能够得到属性值

4、。很多数据结构可以作为索引的数据结构。下面简单描述每个算法的特点。　　数组被用来作为索引结构的优点是他占用的空间最少，而且结构简单，查询速度快。数组最大的缺点就是每次更新时数据移动是O（n）的，因此他在一个动态的环境下是不实用的，但是如果在一个相对静态的环境下，数组是一个不错的选择。　　AT＆TBell实验室Silicon数据库核心组织用AVL树作为索引结构。AVL树被设计为内部存储的数据结构，他是一个二*树，他的检索速度是很快的，这是因为二分检索是树结构的一个本质特性。更新总是影响叶节点可能导致不平衡，因此树必须通过旋转操作来保持平衡。AVL树最大的缺点是他的

5、存储利用率太低。每个树节点仅仅有一个数据项，有2个指针和每个数据项的控制信息。　　B树是比较合适用于磁盘的数据结构，由于他是一个宽而浅的树，查找一个数需要访问很少的节点。大部分数据库系统用一个B树的变种B＋树，他保存所有的数据在树的叶节点上。然而，对于内存数据库，B树比B＋树更合适，因为在内存中保存所有的数据在叶子上并非优点，他太浪费空间。B树的内存利用率是比较好的，所以他用于内存数据库比较合适；搜索速度比较快（用二分查找时，只访问很少一部分节点）；而且更新速度也比较快（数据移动通常只涉及到一个节点）。　　链接的桶Hashing用于磁盘和内存中的静态结构。他非常

6、快因为他是静态结构—不需要重新组织数据。但是，这种优点同时也是他的缺点：因为他是静态的，在一个动态的环境中他几乎不能工作，在填Hash表之前，他的大小必须是已知或可以猜得到的。如果估计的值太小，性能将是很差的，如果估计的值太大，将会浪费很多空间。最好的情况也有一些空间被浪费，因为每个数据项都有一个指针和他相联系。　　可扩展Hashing使用了动态的Hash表，因此表的大小事先不用知道。一个Hash节点可容纳几个数据项，而且当溢出发生时可以分裂成2个节点。目录以2的指数倍增长，只要一个节点溢出而且目录已经达到了指定的最大目录深度，他就会加倍。可扩展Hhashing

7、的一个问题就是任何一个节点都能引起目录分裂，因此如果Hash函数不是很随机的话，目录可能增长的很大。　　线性Hashing也用一个动态的Hash表，但是他与可扩展Hashing有很大不同。和可扩展Hashing相比，当线性Hashing的一个节点分裂的时候，Hash表以预先定义好的线性顺序线性增长。以一种可控制的方式分裂一个节点和扩展目录比可扩展Hashing那种没有控制的分裂要有几个优点：　　（1）桶是顺序排列的，桶的地址可以通过一个基地址计算出来，目录不必要。　　（2）触发一个节点分裂的事件是基于存储空间的利用，这样对一些给定的元素，可以保持存储花费不变。　

8、　改进的线性Hashing比上面介绍的几种更适合于内存。通过用较大的相邻的节点而不是用一个目录，普通的线性Hashing有空节点（当一个节点对应的Hash入口没有数据项的时候）因而浪费空间，除非有一种聪明策略：用底层的虚拟内存映射机制计算出那些当目录增长时不得不拷贝到一个较大内存块的连续节点。改进的线性Hashing用一个很像可扩展Hashing的目录，但是他是线性增长的，而且每个节点只有一条数据，共同从一个内存池里分配内存。分裂的标准是基于性能而不是存储利用率，例如Hash链的平均长度。监视Hash链的平均长度比监视存储利用率在平均搜索花费和更新次数上提供了更

9、直接的控制。　　T树，一