内存数据库存储结构(数据库)
时间：2022-11-05 04:30:01 | 来源：信息时代
时间：2022-11-05 04:30:01 来源：信息时代
内存数据库存储结构 : 内存数据库物理数据的组织方法与具体存储结构。这些物理组织与存储结构是内存数据库总体设计目标(使内存和CPU的利用率尽可能高)的实现基础,其存储结构、索引结构、中间数据存储结构都必须考虑内存的直接存取这一特征。这里介绍几种适合于MMDB的物理组织结构。
1. 区-段式组织结构
区-段式组织结构将存储空间逻辑地划分为“分区”,每一个分区物理地由若干“段”组成。一个段是内存中一个固定长度的连续区域,相当于“页”,是内外存I/O的单位,也是内存空间分配及内存数据库恢复的单位。
区-段式组织结构如图1所示,段中的每个记录有一个唯一标识符(record identifier,Rid),它是一个三元组<i,j,k>,分别表示分区号、段号、段内的记录槽号。记录槽(record slot)包含了对应记录的长度和首地址。每次存取时,由于是内存数据库,存取方法返回的不必是所需记录数据的副本,只需简单地将其槽中的地址返回即可。
图1 区-段式存储结构
2.影子内存式组织结构
影子内存式组织结构将内存数据库空间划分成两部分,一部分是MMDB的主拷贝,另一部分为“影子”拷贝,其体系结构如图2所示。在事务的正常操作期间,每次查询都产生一个分别对于影子内存(shadow memory,SM)和主拷贝(primary database,PDB)的双地址,且总是先对SM试探;若不成功,再对PDB操作。所有的更新操作都在SM中进行,且都记录在活动日志(ative log,AL)中。每当一个事务提交时,由它所产生的在SM中的“后映像”(after image)拷贝到PDB中。
图2 影子内存式存储结构
3.索引式组织结构
B-树、B
+-树仍然是可用的大型动态索引结构之一。但B-树比B
+-树更适合,因为它不像B
+-树那样高层结点码是叶结点中码的重复,叶结点也不含顺序链接指针,所以更省内存。
4. Hash式组织结构
有如下几种形式的Hashing组织结构:
(1)桶散布Hash(如图3所示): 它将码值空间映射到一个“桶散布表”(buckets scatter table)。每一桶由一或少数几块链接组成,链头就是“桶散布表”中的一项,每一这样的链实际就是Hashing“碰撞”的一个“同义链”。
图3 桶散布Hash组织
(2)扩展Hash(如图4所示): 其组织是一个由目录结点和叶结点组成的二层结构。目录由一个指明目录深度d的目录头和2d个指针的目录项组成。深度d表示取伪码(经Hashing后的码)最左的d BIT(位)来定位目录项,伪码就是一个码K经Hash函数变换而得到的一个定长BIT串(见图4)。每一目录项是一个指向叶结点Li的指针。
图4 可扩展Hash组织
(3)线性扩展Hash: 它类似于可扩展Hash,但又具有桶散布Hash的特色,是可扩展Hash与桶散布Hash的结合。其组织结构如图5所示,使用一个可扩展Hash式的目录和桶散布Hash式的块拉链(或桶),不过这里的链不是“碰撞”的“同义链”,而且块的组成也仅是为了提高空间的利用率,它本来是可以单个数据记录地拉链的。
图5 线性可扩展Hash组织
(4)多目录Hash:它是将Hash和索引技术组合的另一种数据组织方法。如图6所示,它首先将码(值)映射成Hash地址,然后划分Hash地址成两部分,分别用来定位和检索相应目录。这里目录的个数N是固定的。
图6 多目录Hash组织
在线咨询
