CN103823865A - 一种数据库主存索引方法 - Google Patents

Abstract

本发明提供了一种数据库主存索引方法，属于计算机数据库高效查询技术领域。本发明采用内存映射方式导入和导出索引文件，替代传统文件读写方式，提高访问效率。在映射区域首地址创建索引头，存储索引基本信息，同时支持多种高效的聚集操作。在映射内存中根据数据表读入索引记录创建索引树，该索引树针对B树索引的缺点进行改进，能够高效地支持重复键，降低存储空间和树的复杂度。随着索引记录的增长，预定大小的文件会出现溢出危险，本发明能有效地对索引文件进行扩容，保证能容纳索引记录而不浪费存储空间。

Description

一种数据库主存索引方法

技术领域

本发明涉及一种数据库主存索引方法，属于计算机数据库高效查询技术领域。

背景技术

随着主存技术的发展,主存的容量越来越大，越来越多的系统是基于主存的，如主存数据库,即将基于磁盘的传统数据库搬进了内存中,明显地提高了系统性能。在数据库中，为了提高查询效率，往往在数据表中的某一主键上创建索引，生成索引文件，将键值直接映射到存储地址，查询则是根据关键字，查询到对应的存储地址后直接访问磁盘并读出字段，这样能明显地提高查询效率。

在传统索引方式中，往往采用频繁的文件读写操作来将索引文件读入内存，这会耗费大量的I/O时间，同时不能保证读入内存索引的完整性，因此影响到索引查询的稳定性能。当对表中的数据进行修改、增加和删除时，索引需要维护，传统的索引由于需要频繁访问磁盘文件而难以维护，这样也就降低了数据表的维护性能。

随着信息时代的发展，数据库表存储的数据量越来越大，对于这样的大文件进行操作,采用传统文件操作方式创建索引效率将非常低，而内存映射技术能有效地节约时间。内存映射是指将一个文件映射到内存中，进程可以像访问内存一样访问文件，而不必调用传统的文件读写函数。由于在映射前，都要预先设置映射文件大小，这样当不断有新纪录插入时，会造成文件溢出，此时必须对索引文件扩容以保证能容纳所有记录同时不浪费内存空间。由于每次映射都是一段连续的地址，采用操作系统的内存分配方法显然是不适用的，因此在映射内存上创建索引树时，需要一套高效的内存管理机制。

常见的索引机制有hash索引、B树索引等，其中hash索引效率高，但是由于其独有特性不支持高效率范围查询，同时不能进行排序，因此未得到广泛应用。而B树索引因为其稳定性高、支持范围查询和排序等特点而得到广泛应用。传统索引方式往往采取多次访问文件的方式进行查询，B树索引利用索引结构层数小的特征，使得访问文件的次数相对较少。

发明内容

为了进一步降低访问磁盘文件的次数和读写时间,本发明在B+树的基础上提出了一种数据库主存索引方法。本发明的目的在于降低数据库查询中索引文件读入内存的时间，并且进一步降低索引检索的时间和索引结构的存储空间，以实现更高效的数据库主存索引技术。

本发明为解决其技术问题采用如下技术方案：

一种数据库主存索引方法，包括如下步骤：

（1）启动数据库系统为某张数据表的主键创建索引时，首先采用内存映射方式将新建的索引文件映射到内存中，在映射内存区域的首地址上创建索引头结构体；

（2）创建索引头结构体后，根据数据表读入索引键值记录，在该映射区域创建索引结构，将索引数据同步刷新到索引文件中；对内存区域的索引结构进行维护操作时，需动态更新索引头信息；

（3）退出数据库系统时，解除内存映射，即可实现在外设磁盘上保存索引结构；当重启系统进行查询时再将索引文件映射入内存，直接将完整的索引结构导入内存中， 实现索引结构的高效率导入和导出。

在对内存区域的索引结构进行维护操作，包括：

 分配和释放内存时，采用链式内存管理机制，将所有空闲块用链表的形式串起来，当为索引记录申请内存空间时，需要利用索引头中指向空闲块的指针，它指向空闲块链表的首节点，该空闲链表的尾节点则位于偏移量对应的位置；分配内存时,根据next遍历空闲块链表直到找到能容纳申请大小的空闲块,更新空闲块链表当释放空间时,初始化该块并遍历链表,找到对应的位置并插入,观察是否和其他块相邻,若相邻则合并。

在申请内存空间时，还包括：

随着索引记录的插入，出现预设的文件大小不足的情况，在索引头中设置一阈值，当文件未分配区域占文件的比例小于该阈值时，断开映射，根据扩容次数对索引文件扩容，当扩容次数越大时，每次扩容比例就越大，扩容次数到一定次数时，设为定值；待扩容完成后，将扩容后的索引文件重新映射入内存。

一种数据库主存索引方法，包括以下步骤：

   除支持唯一索引外，对于重复率较高的键值创建索引的情况，结合hash和B树的特点，采用一种改进的B树索引结构以支持重复键，该索引结构采用链表存储重复键对应的行标示符；

   进行维护操作时，首先要找到相关节点对应的叶子节点，插入时先检查叶子节点是否存在该键值，若不存在，申请内存将该节点插入到该索引树中；若存在则将节点的行标示符插入到该键值对应的链表中，删除时，先删除键值对应链表中的行标示符记录，再检查该链表是否为空，若为空则将该键值从索引树中删除并释放空间；查询和修改都是在叶子节点中找到相应键，在对应的链表中查找和修改记录。

本发明的有益效果如下：

明显降低索引文件读入内存和写回的时间，减少访问索引文件的次数，实现高效的索引结构导入和导出，有效地利用存储空间，支持重复键，在索引记录不断增长时可以动态的对索引文件扩容，同时实现高效率和性能稳定的查询。

附图说明

图1是本发明的原理示意图。

图2是索引文件映射的流程示意图。

图3是带有索引头的B树结构示意图。

图4是改进B树索引叶子节点示意图。

图5是索引文件动态增长示意图。

具体实施方式

下面结合附图对本发明创造做进一步详细说明。

对于大文件采用传统的文件读写方式进行频繁操作会浪费大量的时间，本发明采用内存映射方式存储索引文件来解决该问题，并创建了一种称为索引头（index head）的数据结构来管理映射内存和索引结构。

B树索引支持对重复键进行索引，当键的重复率较高时，传统B树将重复键插入到索引树中,效率非常低，本发明结合hash算法提出了一种支持重复键的改进B树，能有效地减少存储空间和树的复杂度同时保证查询性能。

当后期的维护中，随着索引记录逐步插入，索引文件会有超过预设大小的危险，本发明采用一种索引文件动态增长机制进行扩容，以保证拥有足够空间容纳索引记录，不会出现溢出现象，同时不浪费存储空间，这样保证了系统良好的可拓展性。

内存映射（memory map）技术可以将一个文件的一部分或全部映射进内存中。如图1所示，索引文件全部映射入内存中，映射范围即文件大小，这样对文件的操作可以直接用指针进行，操作系统可以将内存数据刷新到相应的文件中，以实现索引文件的动态更新。

本发明实施方式采用的技术就是内存映射技术，采用mmap()函数将索引文件按照一定方式和大小映射入内存，得到映射的基地址，映射入内存后无需再访问索引文件，只需访问映射的索引内存，这样即可节省索引文件读写时间。当所有操作完成退出系统后，使用munmap()函数将该段内存重新映射回索引文件，即完成了索引更新。由于索引文件映射到内存的地址可设置为固定和系统分配两种模式，考虑到一旦固定起始地址，当该段内存事先被系统其他进程占用时，系统的可移植性将不能得到保证，所以本发明采用系统分配的方式，这样每次映射的地址不相同，所以节点中的指针并不能存储真实地址，而是存储地址对应的偏移量，该偏移量即为存储地址和基地址（base_ptr）之差；访问指针所指变量时，则需加上基地址。

下面通过说明书附图对各实施例对本发明进行说明。

1） 实施例一

本发明的实施例一介绍了一种索引文件导入内存的方法，具体步骤流程如图2所示,包括:

A、 检查是否存在索引，若存在则执行步骤B；否则执行步骤G；

B、  根据数据表记录数估计索引文件大小，并根据表名、列名创建相应大小的索引文件；

C、  按照一定的读写方式，设置好文件偏移量和映射长度将索引文件映射入内存，映射方式采取随机映射方式，即由系统随机分配内存，映射完成后返回基地址；

D、 在基地址上创建索引头，进行初始化，将指针指向偏移量对应的内存空闲块；

E、  根据数据记录依次获得索引记录；

F、  若为第一条记录，遍历链表申请空间创建索引树；否则遍历链表申请空间将节点插入到索引树中，具体详见实施例二中的插入步骤；

G、  进行查询、删除、修改、插入等操作；

H、 退出系统，解除内存映射。

2）实施例二

本发明的实施例二如图3、4所示，展示了改进的索引结构以及B树数据结构，图3表示改进的B树索引结构，它包含了索引头，其中索引头分别指向了根节点、叶子链表首节点和尾节点，这样就能快速找到根节点，进行插入、删除、查询、修改等操作，同时能获得最大和最小键值索引记录，以方便进行聚集操作。本发明B树的具体改进部分如图4所示，它主要对重复键值的存储进行了改进，将重复的键值记录存储到键值对应的行标示符链表中，这样就能避免将该记录插入到整个索引树中，而避免了进行分裂等复杂操作。

实施例二主要包括插入、删除、查询和修改四个步骤，如下所示：

1、插入操作步骤

A、输入待插入的索引记录（key，rowid）；

B、 根据索引头读取根节点root；

C、 遍历索引树进行键值key比较寻找相应的叶节点；

D、 如果找到叶节点，执行步骤E；否则该树为空，根据（key，rowid）创建索引树；

E、  在该叶节点中寻找是否存在key；

F、如果不存在，执行步骤G；否则执行步骤I；

G、 将其插入到该节点中，检查插入后的节点是否溢出，若溢出插入到父节点中，则执行步骤H；否则执行步骤J；

H、 检查父节点是否溢出，若溢出则进行分裂和插入到父节点的操作，逐步迭代；否则执行步骤J；

I、遍历该键值对于的链表查询是否存在行标示符rowid，若无则将其按序插入键值key指向的链表中，否则插入失败；

J、返回根节点，更新索引头。

2、删除操作步骤

A、输入待删索引记录（key，rowid）；

B、 根据索引头读取根节点root；

C、 遍历树进行键值key比较寻找相应的叶节点；

D、  若找到相应叶节点，执行步骤E；否则表示树为空，退出；

E、  在该叶节点中查找键值key，若找到，执行步骤F；否则未找到相应节点，删除失败，退出；

F、 在对应的链表中查找行标示符rowid，若找到则删除；否则删除失败，退出；

G、 检查键值key对应的链表是否为空，若为空则将键值key节点删除；

H、 成功删除索引记录，更新索引头。

3、查询操作步骤

A、 输入待删索引键值key；

B、  根据索引头读取根节点root；

C、   遍历树进行键值key比较寻找相应的叶节点；

D、   若找到叶节点，执行步骤E；否则树为空，退出；

E、  在该叶节点中查找键值key，若发现则返回其指向的链表首地址；否则退出，未找到相应记录。

4、修改操作步骤

A、 输入待修改索引记录（key，rowid_old，rowed_new）；

B、  根据索引头读取根节点root；

C、  遍历树进行键值key比较寻找相应的叶节点；

D、  若找到叶节点，执行步骤E；否则树为空，退出；

E、  在该叶节点中查找键值key，若发现执行步骤F，否则退出；

F、   在key对应的链表中查找老的行标示符rowid_old，查找到后，修改rowid_old为新标示符rowid_new，修改成功，更新索引头；否则不存在，修改失败退出。

3）  实施例三

实施例三提供了一种索引文件动态扩容机制，该方法的步骤流程如图5所示，包括：

A、检查未分配内存大小free_len与待分配大小之差占总大小的比例是否小于索引头中定义的阈值（5%）；

B、若小于，执行步骤C；否则执行步骤G；

C、断开映射，写回磁盘文件；

D、获取索引头中定义的扩容次数extend_time和目前索引文件大小index_file_len；

E、计算索引文件扩容大小；

扩容大小extend_size与扩容次数extend_time和目前索引文件大小index_file_len两个因素有关有关:

若扩容次数不超过2次

        扩容大小等于索引文件长度*(2*扩容次数+1)*10%;

      否则

             扩容大小等于索引文件长度*50%;

F、  扩容后重新映射索引文件到内存；

G、 继续进行相关操作。 

Claims (4)

1.一种数据库主存索引方法，其特征在于包括如下步骤：

（1）启动数据库系统为某张数据表的主键创建索引时，首先采用内存映射方式将新建的索引文件映射到内存中，在映射内存区域的首地址上创建索引头结构体；

（2）创建索引头结构体后，根据数据表读入索引键值记录，在该映射区域创建索引结构，将索引数据同步刷新到索引文件中；对内存区域的索引结构进行维护操作时，需动态更新索引头信息；

（3）退出数据库系统时，解除内存映射，即可实现在外设磁盘上保存索引结构；当重启系统进行查询时再将索引文件映射入内存，直接将完整的索引结构导入内存中， 实现索引结构的高效率导入和导出。

2.如权利要求1的一种数据库主存索引方法，其特征在于在对内存区域的索引结构进行维护操作，包括：

    分配和释放内存时，采用链式内存管理机制，将所有空闲块用链表的形式串起来，当为索引记录申请内存空间时，需要利用索引头中指向空闲块的指针，它指向空闲块链表的首节点，该空闲链表的尾节点则位于偏移量对应的位置；分配内存时,根据next遍历空闲块链表直到找到能容纳申请大小的空闲块,更新空闲块链表当释放空间时,初始化该块并遍历链表,找到对应的位置并插入,观察是否和其他块相邻,若相邻则合并。

3.如权利要求2所述的一种数据库主存索引方法，其特征在于，在申请内存空间时，还包括：

随着索引记录的插入，出现预设的文件大小不足的情况，在索引头中设置一阈值，当文件未分配区域占文件的比例小于该阈值时，断开映射，根据扩容次数对索引文件扩容，当扩容次数越大时，每次扩容比例就越大，扩容次数到一定次数时，设为定值；待扩容完成后，将扩容后的索引文件重新映射入内存。

4.一种数据库主存索引方法，其特征在于，包括以下步骤：

    除支持唯一索引外，对于重复率较高的键值创建索引的情况，结合hash和B树的特点，采用一种改进的B树索引结构以支持重复键，该索引结构采用链表存储重复键对应的行标示符；

    进行维护操作时，首先要找到相关节点对应的叶子节点，插入时先检查叶子节点是否存在该键值，若不存在，申请内存将该节点插入到该索引树中；若存在则将节点的行标示符插入到该键值对应的链表中，删除时，先删除键值对应链表中的行标示符记录，再检查该链表是否为空，若为空则将该键值从索引树中删除并释放空间；查询和修改都是在叶子节点中找到相应键，在对应的链表中查找和修改记录。

Images