《内存数据库数据组织结构 存储模型》由会员分享，可在线阅读，更多相关《内存数据库数据组织结构 存储模型（5页珍藏版）》请在金锄头文库上搜索。
1、2.4内存数据库数据组织结构记录数据组织结构：区段式数据组织结构区号段号段内槽号关系表关系表关系表3数据区索引区数据区索引区数据区 索引区关系表数据区索引区1r1F索引数据段1记录数据段1索引数据段2记录数据段2-索引数据段11记录数据段n记录记录记录记录段内系统信息记录槽4记录槽3记录槽2记录槽1在关系数据库往往使用区段式的数据组织结构，区段式数据组织结构将共享内存划分为若干个“分区”，每个分区存储关系数据库的一个关系。每个分区又是由若干固定长度的“段“（也称作”页“）组成，一个段往往是共享内存动态分配的一个单位。而数据库具体的数 据记录则保存在段中分配的一个记录块中。在采用区段式的数据组织
2、 结构的数据库中，一个记录的地址信息由一个三元组P,S,L标志， 其中 P 是分区号，一般对应于一个关系表名， S 是段号，标志组成这 个分区的具体的段，L是段内记录槽号，主要保存了记录在段内的偏 移和长度，用来在段内进行寻址。从而通过这个三元组可以唯一的定 位一个记录的具体位置。2.4.2 索引的结构2.4.2.1 hash 索引hash 索引定义了一个 hash 函数，通过将关系表的索引项传入到 hash 函数可以计算出相应的hash值，从而在索引项和hash值之间建立起 对应关系。同时用于保存不同的 hash 值的索引信息首地址往往是线 性结构，从而可以迅速的找到每个hash值的首地址，
3、使得通过hash 索引查找数据只需常数时间的复杂度。hash 索引的示意图如图2.7 所示：由图2.7可知，往往索引项不同的具体数据使用hash往往会得到相同 的hash值，所以一般为每个hash值建立一个动态的冲突链表来保存 同一 hash 值的记录索引信息。当为一条记录建立索引时只需通过对 索引项使用hash函数的到其hash值，通过计算得到的hash值迅速找 到保存此 hash 值冲突链的首地址，并将这条记录的地址信息插入到 冲突链表中。当需要通过这个索引项的一个特定值对记录查找时，只 需对这个索引项的给定的值运用hash函数求的hash值，找到该hash 值冲突链的首地址，顺序遍历冲突
4、链以找到待查找的记录的地址息。2.4.2.2 T 树索引当使用 T 树索引时，插入，删除和查询索引主要设计到的操作有树的中序遍历，树的平衡，树的旋转和节点内数据的维护。2.5内存数据库存储模型N-Array存储模型所谓N-Array存储模型即是将数据库关系表的记录在数据页面顺序存放。即将一条记录的所有字段的数据顺序存放在连续的空间。N-Array存储模型示意图如图2.9所示：内存页头部SlutlSlut?Slot31F记录3FieldFieldField记录2FieldFieldHi Field记录1FieldFieldField图2 N-Airay存储模型示意图N-Array模型将整条记录顺序存放在数据页面中，通过一个包含记录 业内偏移和记录长度的结构体在数据页面中定位记录。通过这种方式N-Array模型内够有效的使用数据页面的额存储空间。但是使N-Array 存储模型时，进行数据查找每次找到的都是一整条记录，因而当只需 查找关系表的某几个字段或对几个关系表进行联合查找时则会浪费 过多的缓存空间，从而造成较大的开销，由此可见N-Array存储模型 的缺点在于不能很好的支持对缓存效率的要求。当前主流内存数据库SQLite，fastDB，eXtremDB样都将记录以 N-Array的模型进行存储。
