内存数据库索引结构(数据库)

时间：2022-11-04 06:30:01 | 来源：信息时代

时间：2022-11-04 06:30:01 来源：信息时代

    内存数据库索引结构 : 内存数据库索引结构是为具有特定属性值的MMDB数据提供指针,以实现快速存取的一种专门数据结构。内存数据库索引的概念与DRDB完全一样,所以原则上一般索引结构也可用于MMDB。但由于对内存数据库而言,“时-空”这对矛盾的地位正好对调,因此各种索引结构在内存数据库中表现出与原来不同的特征。另外还开发出了许多适合内存数据库的专门索引结构。
1. 一般内存索引
适用于MMDB的索引结构可分为两大类: 一是数据保持某种自然排序,如各种树结构; 另一类是数据随机分布,如各种Hash索引结构。常用的内存数据库索引结构有:
(1)数组: 在IBM的内存数据库系统OBE中,采用数组作索引结构。它使用的空间最小,但每一维护操作所引起的数据移动量是O(N)级的(N为数组元素个数)。其代价太高,除只读(read-only)环境外,几乎没有什么实用性。
(2) AVL树: AT&T BeLL实验室的“硅数据库机”(silicon database machine)中用它作内存索引结构。它的操作时间复杂度为O(Log₂N)(N为记录数),因此具有较高的存取性能。但每个结点只有一个数据元素,却有两个指针和有关控制信息,其内存的有效利用率很低。
(3) B-树: 操作性能好,且能动态维护。但它的内存有效利用率很低,因为①结点空间的平均占用率约66%,且其阶K越大,虽然操作性能越好,但每一结点的绝对未用空间就越大; ②任一结点中若有m个数据元素(索引码),则有(m+1)+m个(对于内结点)或0+m个(对于叶结点)指针(后一个m是指向数据记录的指针数),指针占用空间的比例太多。
(4) B⁺-树: 在内存情况下,B⁺-树不具有比B-树更大的优越性。
2. SB-树索引结构
兼有AVL树和B-树的主要特征,是一种满足下列条件的树结构(D,E),其中D为其结点集,E为边集:
(1) D中存在唯一的称为根的结点r,无父辈。
(2) D={r}∪D_L^r∪D_R^r, D_L^r∩D_R^r＝∅; 且存在唯-X_R^r∈D_L^r,X_L^r∈D_L^r,使得E={<r,X_L^r>,<r,X_R^r>,E_L^r,E_R^r}。
(3)(D_L^r,E_L^r),(D_R^r,E_R^r)是符合本定义的SB-树,分别称为根r的以X_L^r和X_R^r为根的左子树和右子树,且它们是平衡的,即|h_L^r-h_R^r|≤1(h_L^r和h_R^r分别为左、右子树的高度)。
(4)结点N的形式为(bf,lc,rc,lp,rp;e₀,e₁,…,e_n,…,e_2n)(见图1),其中:①bf=h_L^N-h_R^N,称为N的平衡因子; ②lp和rp分别为指向左、右子树的指针; ③lc和rc分别为左半部e_i(0≤i≤n-1)和右半部e_i(n+1≤i≤2n)的实际个数; ④所有元素e_i(i=0,1,…,2n)构成一个标识顺序集: ∀e_i＝K_i∈N,K_i<K_i+1(i=0,1,…,2n-1);⑤若N为叶结点,则1≤(lc+rc+1)≤2n+1;否则2n+1-m≤(lc+rc+1)≤2n+1。n称为SB-树的阶,m为很小的正整数,表示空元素个数。

图1 SB-树结点的结构

(5)对任一结点N, 若D_L^N≠∅, D_R^N≠∅, 则在N的左子树中存在所有码值最大者K_max^N,其元素e_max^N称为N的最大下界,其结点N_max^N称为N的最大下界结点。同样,在N的右子树中有N的最小上界码值K_min^N及其元素e_min^N和最小上界结点N_min^N,且K_max^N

。SB-树整体结构如图2所示。

图2 SB-树结构

3.SB-树的性能
(1)查找性能:①具有N个索引项(或数据记录)的SB-树的最大高度h为h<1.44log₂(N+2n+1-m)-1.44log₂(2n+1-m)+1。②最坏情况下查找的时间复杂度为0(log₂(N+2n))+0(Blog₂n),其中B为结点内的二分查找代价。
(2)存储空间:①设结点的格式与大小一样,令bf、rc、lc各一字节,lp、rp是两个指针,2n+1个Rid实际上也是指针,令指针长度为PR,则其存储记录大小为S_N＝3+2PR+(2n+1)PR=(2n+3)PR+3字节。②SB-树的存储空间依赖于其是否成块,若不成块,则N个数据记录的n阶SB-树的结点数为

其存储空间为ST=S_N×N_n。若成块,设BS为块的大小,则组成因子为

其存储空间为

(3)性能比较:将SB-树和代表性的B-树、AVL树的性能进实验测试比较,其结果如下: ①插入:SB-树最好。因为它的查找时间接近于AVL树,但没有那么多的内存分配和旋转操作; 它具有类似于B-树的维护特征,但没有B-树的结点内和结点间的数据移动。②查找: AVL树最好,因无结点内的查找; SB-树比B-树好,因为在搜索路径上,不需要对每一结点进行二分查找,只需比较其最大(右)和最小(左)元素即可。③存储代价: SB-树最好,B-树次之,AVL-树最差。
综上所述,SB-树综合性能最优,AVL树的存取性能最优,但存储性能明显低于B-树。