内存数据库索引技术研究

1、第第卷第期卷第期电脑与信息技术年月文章编号：（）内存数据库索引技术研究邹乐天（中国人寿保险公司湖南分公司，湖南长沙）摘要：内存数据库已经成为了当今数据库研究的热点，而索引能够极大地提高数据库操作的性能。文章介绍了内存数据库发展至今比较成熟的一些索引结构，并在查找时间上对它们进行了对比分析，总结了结构特点和分析数据之后的结论表明，树索引和树索引有着最好的缓存意识，同时还具有很高的查找速度和空间利用率。关键词：内存数据库；索引；树；树中图分类号：文献标识码：（，）：，：；合的索引结构也就自然而然的成了研究者关引言随着大容量内存越来越便宜，现在配置一台大内注的问题。存的计算机也越来越容易。对数据库系

2、统而言，已经有条件将数据库的“主版本”常驻内存，这样可使系统事务的状性能获得很大的改善，如操作大量减少、态转换及其相联高速缓存的替换大量减少、锁的竞争下降，更有效的内存查找结构和查询处理可以被使用等。数据库的“工作版本”或者整个数据库都常驻内存的数据库系统被称为内存数据库（，经典索引结构早在世纪年代，便有学者开始研究的索引。至今，这些索引结构已经成为了经典，主要是下面这些。数组（）最早使用数组来做的索引。在预先知道大小，或者其数据的增长不会造成问题的情况下，数组索引可以有最佳的空间利用率。但其缺点也显而易见，每次更新数据的时候，其数据移动的量是（）级，所以如果只是一个只读的环境，那么就可以使用

3、数组来做索引。）。由于内存系统与磁盘系统具有不同的特性，因而与磁盘数据库（，存储格式、尤其是查询处理等方面都）在性能、有着比较大的差别。系统的“瓶颈”是磁盘，故查询处理的优化策略主要是针对减少磁盘的存取次数的，并且尽量存储临时结果，以“空间”换“时间”。而在中，由于内存空间及其宝贵，其查询处理算法则要极力减少比较次数，并且尽量不存储临时结果，以“时间”换“空间”。在这样的前提下，原有的的索引结构对来说就不再适用了，研究新的适树树索引是在和贝尔实验室中诞生的，其本质上是一个二叉树，树的结点结构如图所示。因为使用二分查找，所以树查找速度很快。由于数据的更新会对叶结点有影响，故有可能破坏树的平衡，而

4、要通过“旋转”操作来维护树的平衡。但其维护性能是比较好的，最多就是一个“双旋转”操作的代价。收稿日期：；修订日期：作者简介：邹乐天（），男，湖南娄底人，高级程序员，研究方向：数据库管理。电脑与信息技术年月另外，树可不包含任何块（或页）结构，其索引记录可直接定位。然而，有一个很大的缺点，就是其存储利用率很低，每一结点只存储一个数据项，却有两个指针和一些有关的控制信息。数据结点控制结点左指针右指针图树结点树树是一种非常适合磁盘数据库系统的索引结构，因其树型结构宽而浅，查找数据只需要短短的几步即可完成。树，尤其是其变种树，在大多数现有数据库系统中已被广泛使用。但是在内存中，树比树更合适，因为像树那样

5、在叶结点中包含所有数据只是白浪费空间，并且相比之下树拥有更高的查找和更新效率。树的结点结构如图所示：控制结点数据数据数据图树结点索引（）链式桶。链式桶对每一个文件都有一个函数，它将该文件的关键字值空间映射到一个“桶散布表”（），结构如图所示。每一桶由一块或少数几个块链接组成，链头就是“桶散布表”中的一项，每一链实际就是“碰撞”的一个“同义链”。因为链式桶是一种静态索引结构，所以其查询相当快。正因为如此，使得其事先要比较准确的知道表的大小，太小效率会很低，太大则浪费空间。图链式桶（）可扩展。可扩展使用随数据增长的动态表，当达到溢出的临界条件时，一个结点将分裂成两个，以此来实现动态增长。这种组织克

6、服了上述链接桶的静态性，不必事先知道文件的记录数。但这种组织的一个问题是，如选择的函数不是充分随机的，则可使目录变得很大，结构如图所示：图可扩展（）线性。线性也是使用动态表，它类似于可扩展，但又具有链式桶的特色，结构如图所示。它使用一个与可扩展一样的目录，但数据块的组织却具有链式桶式的特色，即有拉链的桶。不过这里链的语义与链式桶的不一样，它不是“碰撞”的“同义链”，而且这里桶的组成也仅是为了提高空间的利用率，它本来是可以记录单个数据的拉链的。图线性树树是将树和树结合在一起而得出的一种新的数据结构，树也是一种二叉树，只不过每个结点（称为结点）都包含多个元素。每个结点都包含一系列从小到大排序后的元

7、素和三个指针，指针分别指向父结点和左右结点。某一结点的左结点中必会包含比结点中最小元素小的最大元素，而结点的右结点中必会包含比结点中最大元素大的最小元素。因为是二叉树，所以树具有树固有的二分查找特性，又因为每个结点包含多个元素，其又包含了树良好的更新和存储特性的优点。对树来说，因插入和删除数据所造成的数据移动通常可以局限在一个结点内进行，和树一样，树也是通过旋转来使树达到平衡的，但其所需要的旋转操作的次数远少于树。树的结点结构如图所示：指向父结点数据数据数据数据控制结点指向左孩子指向右孩子图树结点第卷第期邹乐天：内存数据库索引技术研究缓存意识的索引结构随着技术的日益发达，系统缓存也变得越来），

8、简称树。树是数组索引的改进，其树结构如图所示。树在一个排序数组的顶端存储一个目录结构，这个目录将自己数组的物理结构描述成一个平衡查找树，结点在数组中按从上到下，从左到右的顺序排列。因为这个目录结构，树可以获得比二叉树更高的查找效率，并且与树相比，树避免了在每个结点中都储存个子指针，通过选择结点存储值的个数，可以达到在一个缓存块中刚好存储一个结点，这样可以极大提高存储效率，更有利于数据的存放，增加缓存的命中率。越大。经典索引结构在设计时没有考虑索引对缓存的利用率问题，因而不能充分发挥索引的性能。现今的研究人员在缓存利用率上做文章，对索引进行了改进，以提高时间和空间利用率，其中比较具有代表性的索引

9、结构如下：（）树在提高索引的查找效率且不占用较多的额外空间的前提下，文献提出了一种新的索引结构缓存敏感查找树（中间结点叶子结点图树树又可以分为满树和层次树两种。一个满树的每个结点可以保存个数的值，可以根据缓存块的大小来选择。层次树的定义与满树稍有不同，其每个结点保存的数值的个数为，其中（为自然数），这样可以使结点中的值构成一个完全二叉树，在查找的时候可以减少数据比对的次数，从而提高查找效率。不过需要注意的是，在相同的情况下，因为每个结点保存的值较满树要少，故层次树需要比满树更多的存储空间。（）树个结点的子结点们分段存储，该结点保存指向这些段的指针，段中的结点被连续排列。满树被定义为预先分配结点

10、组空间的树，在结点分裂时，满树只需要移动结点组的部分结点，减少了处理时间，但预先分配空间意味着增大了空间开销，这也是典型的空间换时间的例子。树是一种静态索引结构，因而一旦数据发生变化，索引必须被重建。这种局限性注定了树会被改进。受文献的启发，哥伦比亚大学的等对树做了改进，提出了树索引（）。树的结构与树类似，不同的是树把一个结点的所有子结点都存储在一个连续的数组中，只保存个指向第一个子结点的指针，其它子结点的位置通过计算位移量来得到。因为只保存个子结点的指针，所以个结点可以有空间来保存更多的值，这样可以节省存储空间，并且，由于一个缓存块往往可以满足不止一层的数据比对，因而可以减少查找过程对缓存块

11、的需求。树的结构如图所示，其中被虚线框框在一起的结点被称为一个结点组。图树性能分析本节将前面所提到的索引结构列在一起，在查找的时间性能上做了分析，结果见表。表索引结构分歧因子索引的查找时间性能分析比较次数缓存未击中率树树树满树层次树（）（）（）（）（）（）树段树满树树又可衍生出段树和满两种结构。段树为了避免结点分裂时拷贝整个结点组，将一电脑与信息技术年月综合各索引结构的特点和表的数据可以得出下面的结论：树在数据连续存储时几乎不需要额外的存储空间，但其查找时间开销很大。索引的空间开销很大，但在随机查找时具有最好的时间性能。树因为其较差的缓存击中率，导致查找开销比较大。树在缓存意识上比树和树都要好

12、，但因为每个结点保存个值和个子指针，所以结点利用率不高。树和树有着最好的缓存意识，缓存块利用率最好，并且查找速度要快于树，同时也能节省结点空间。和性能分析数据，对各个索引的优缺点进行了总结。结论表明，树和树有着最好的缓存意识，同时还具有很高的查找速度和空间利用率。参考文献：刘云生现代数据库技术北京：国防工业出版社，结束语内存数据库是当今数据库研究的热点，而索引结构对数据库的性能至关重要。由于内存系统和磁盘系统的不同特性，有必要重新设计适合于的索引结构。本文将当前的具有代表性的索引结构，包括经典索引和改进的缓存意识的索引分别进行了介绍，并对其查找时间性能做了分析；根据索引结构特点，：，：，：，：

13、! （上接第页）采用逆序算法都可以实现批量操作，逆序算法包括逆序逐点插入（或删除）算法和逆序结点群插入（或删除）算法两种。在完成一次副表的插入（或删除）后，应该马上形成汇总表，以避免出错。逆序算法与分级定位查找相配合，可以构成一种高效率的动态查找算法。参考文献：陈启星，罗启宇分档定位排序以及向分档定位查找的发展计算机研究与发展，（）：，程序设计教程（第版）薛万鹏，等译北京：机械工业出版社，严蔚敏，吴伟民数据结构（第版）北京：清华大学出版社，! （上接第页）结构基础上引入超级节点的概念，模型将节点按能力不同（计算能力、内存大小、连接带宽、网络滞留时间等）区分为普通节点和搜索节点两类（也可以进一步分为三类节点，其思想本质相同）。其中搜索节点与其临近的若干普通节点之间构成一个自治的簇，簇内采用集中式对等网络模型，而整个网络中各个不同的簇之间再通过纯的模式将搜索节点相连起来，甚至也可以在各个搜索节点之间再次选取性能最优的节点，或者另外引入新的性能最优的节点作为索引节点来保存整个网络中可以利用的搜索节点信息，并且负责维护整个网络的结构。这样就极为有效地消除纯时，由于每个簇中的搜索节点监控着所有普通节点的行为，这也能确保一些恶意的攻击行为在局部得到控制，并且超级节点的存在也