面向结构化数据的分布式内存数据库索引方法

摘要

本发明公开了面向结构化数据的分布式内存数据库索引方法，述方法包括：接收数据库操作请求；根据所述数据操作请求，在数据库中对待操作关键值进行索引操作，所述索引包括：分布式索引和底层单机索引；其中，所述分布式索引包括：数据分布索引和行分布索引；所述数据分布索引负责数据和行表的跨机定位；所述底层单机索引为细粒度的数据级索引；所述单机索引包括：列式压缩索引和行表；所述列式压缩索引由三个向量组成：字典、频数向量、行号索引，所述行表负责维护各个记录项的行号到其所在字典下标的映射，实现了能够高效的存储索引，能够利用索引快速查询数据，对索引进行压缩处理，降低了内存需求的技术效果。

说明书

技术领域

本发明涉及计算机软件领域，尤其涉及一种面向结构化数据的分布式内存数 据库索引方法。

背景技术

随着计算机硬件水平的发展，内存的价格变得可以被大家接受，由于内存相 比硬盘存储速度更快，可以更好的进行查询和访问，因此，越来越多的人们开始 研究在内存中实现数据存储。同时，在信息化社会，大规模数据存储已经变得十 分的普遍，为了在分布式环境下利用内存设计数据库，满足OLAP的需要，我们 研究和设计了分布式内存数据库系统。对于数据库而言，数据库索引技术是其中 最为重要的一部分，如何高效地存储索引以及利用索引快速查询数据是设计数据 库的关键所在。另外，由于是内存数据库，内存资源相对宝贵，而索引占用了较 多的内存。

综上所述，本申请发明人在实现本申请实施例中发明技术方案的过程中，发 现上述技术至少存在如下技术问题：

在现有技术中，现有的分布式内存数据库系统索引存在存储索引效率较低， 占用内存较多的技术问题。

发明内容

本发明提供了一种面向结构化数据的分布式内存数据库索引方法，解决了现 有的分布式内存数据库系统索引存在存储索引效率较低，占用内存较多的技术问 题，实现了能够高效的存储索引，能够利用索引快速查询数据，对索引进行压缩 处理，降低了内存需求的技术效果。

在当前的技术领域，并没有如何构建符合分布式内存数据库特征的索引技术 的公开化资料，本专利的核心目的就是提出一种可行的，经过系统验证的分布式 内存数据库的索引构建和存储技术。

其中，名词解释：

MDE：MemoryDataEngine，内存数据库引擎

DS：DataServer，数据导入模块，负责将原生数据源数据导入内存数据库 存储引擎中；

CS：ColumnStore，MDE中存储数据的服务节点；

IS：IndexServer，MDE的Master节点，负责存储元数据，子表索引，负 载均衡等；

字典:CS中用于数据检索的必要数据结构；

数据分布索引：数据库中的表的每列有一个数据分布索引，索引该列某范围 数据在CS上的分布；

切片:数据分布索引会把原始列数据切成n段，每一段成为一个切片；

RAS：ResourceAllocationSystem，资源分配与管理子系统；

行压缩表:对原表进行数据压缩生成的行表；

单列压缩表:对单列数据进行排序压缩后生成的单列表；

行分布索引：IS中保存的行压缩表在CS集群中分布的索引；

行压缩表子表：对行压缩表进行按行切分后生成的子表。

为解决上述技术问题，本申请实施例提供了一种面向结构化数据的分布式内 存数据库索引方法，所述方法包括：

接收数据库操作请求；

根据所述数据操作请求，在数据库中对待操作关键值进行索引操作，其中， 所述索引包括：

分布式索引和底层单机索引；其中，所述分布式索引包括：数据分布索引和 行分布索引；所述数据分布索引存储在具有master角色的控制节点中，负责数 据和行表的跨机定位；

所述底层单机索引为细粒度的数据级索引；所述单机索引由两套相对独立的 索引集合构成，包括：列式压缩索引和行表；所述列式压缩索引由三个向量组成： 字典、频数向量、行号索引，所述行表负责维护各个记录项的行号到其所在字典 下标的映射。

进一步的，所述数据库索引在执行一个典型的关系型查询时关键步骤如下：

对于查询SELECTnameFROMteacherWHEREage>30；

步骤1：首先从控制节点中获取数据分布索引，得到待查询表某一列(上述 语句中的teacher表age列)所在节点的定位信息；

步骤2：连接该节点并根据查询中的过滤条件(age>30)获取该列满足条件 的记录项的行号；

步骤3：从控制节点获取待查询表的行表(teacher表)所在的节点定位信息；

步骤4：连接行表所在的节点并根据步骤2获取的行号集合获取待查询其它 列(上述例子中的投影列name列)待获取记录项对应的字典下标索引；

步骤5：将步骤4得到的字典下标索引发送给控制节点，从控制节点获取该 字典所在列(name列)的节点信息，控制节点将字典索引发送给对应列所在节 点；

步骤6：步骤5中的列节点(nanme列)收到控制节点发送来的字典索引信息 后，通过该索引信息取出满足查询语句中约束条件的记录，查询结束。

进一步的，所述定位信息具体为：节点号或IP。

进一步的，所述连接该节点并根据查询中的过滤条件获取该列满足条件的记 录项的行号，具体为：连接该节点并根据查询中的过滤条件，采用二分查找，在 O(logN)时间复杂度下获取结果集合，获取该列满足条件的记录项的行号。

进一步的，所述数据库采用列式存储的方式，压缩后的原始数据以列为单位 进行分布和存储，不同列之间的相关性由源数据库中的rowkey来决定，对处理 过后的列数据进行切分，并分布式存储；同时对切片数据建立数据分布索引，用 来切片的定位；切分后的列数据做局部的字典压缩处理。

进一步的，原始数据采用字典压缩和按位压缩两种方式进行处理。

本申请实施例中提供的一个或多个技术方案，至少具有如下技术效果或优 点：

由于采用了字典压缩以及位压缩技术手段，利用字典压缩对重复数据进行去 重处理，避免存储多余的冗余数据，在存储列压缩索引频数向量和行号索引向量 中采用位压缩手段，充分利用物理内存，显著提高内存存储的利用率，所以，有 效解决了现有的分布式内存数据库系统索引存在存储索引效率较低，利用索引查 询数据速度较慢，占用内存较多的技术问题，进而实现了能够高效的存储索引， 能够利用索引快速查询数据，对索引进行压缩处理，降低了内存需求的技术效果。

附图说明

图1是name列的数据分布索引与全局字典示意图；

图2是底层数据索引结构示意图；

图3是行分布索引建立流程示意图；

图4是数据导入流程示意图；

图5是原始数据排序流程示意图；

图6是底层索引辅助向量生成流程示意图；

图7是原始数据压缩、切片和行压缩表子表填充流程示意图；

图8是索引数据切分和数据分布索引建立流程示意图；

图9是数据分布索引发送给IS流程示意图；

图10是CS启动示意图；

图11是底层数据和底层数据索引发送给CS流程示意图；

图12是CS中行压缩表子表示意图；

图13是IS中的数据结构示意图；

图14是列式压缩索引由三个向量以及行压缩表结构示意图。

具体实施方式

本发明提供了一种面向结构化数据的分布式内存数据库索引方法，解决了现 有的分布式内存数据库系统索引存在存储索引效率较低，占用内存较多的技术问 题，实现了能够高效的存储索引，能够利用索引快速查询数据，对索引进行压缩 处理，降低了内存需求的技术效果。

为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式 对上述技术方案进行详细的说明。

实施例一：

在实施例一中，提供了面向结构化数据的分布式内存数据库索引方法，包括：

接收数据库操作请求；

根据所述数据操作请求，在数据库中对待操作关键值进行索引操作。

其中，索引包括：

数据分布索引和字典：

为了应对OLAP数据库对列大量的操作，本数据库采用列式存储的方式，压 缩后的原始数据以列为单位进行分布和存储。不同列之间的相关性由源数据库中 的rowkey来决定，对处理过后的列数据进行切分，分布式存储，同时对切片数 据建立数据分布索引，用来切片的定位。切分后的列数据做局部的字典压缩，节 约内存存储空间。

按图1所示，name列的数据分布索引由一个map组成，key为一对pair， value为对应切片的ip所在。其中key内含对应切片中的数据的上限和下限， 而具体的上限和下限又由两个内层pair组成，分别为具体的值和字典entry。

数据压缩：

由于内存资源宝贵，所以原始数据采用字典压缩和按位压缩两种方式。字典 压缩是将原本出现频数大于一的内容只存储一份，这种压缩对于出现频率很高的 内容非常有效。按位压缩，根据数据的最大值精确到位的个数，重新组织该列的 数据类型，完成二次压缩。

分布式联合索引：

单列存储引擎中的数据组织为以下三个向量。

排序字典。

I^j：索引偏移量向量，确定字典中每一项起始和截止位置。

P^j：主键存储向量，存储列中具体值的主键位置，是列值的倒排索引，请参 考图2。

其中I^j和P^j的大小求法如下所示：

$sizeof\left(I^j\right)=\left(\right|U_M^j|+1)·\frac{A^j}{8}bytes$

$sizeof\left(P^j\right)=N_M·\frac{A^j}{8}bytes$

这样做有三个好处：

因为列值是排序存储的，用三种向量就可以消除重复数据，减少单列存储的 代价；在做范围查询的时候，不需要搜索全列，只需要按序找到上下界；有增量 数据合并，导致索引重建时，只有O(n)的时间复杂度。

索引构建流程：

如图3，从源数据库(Oracle等)中读取整表数据(或仅是一些元数据信息)， 得到数据规模以及字段数，建立行分布索引。

根据rowkey的数据分布索引将建行压缩表子表的命令发给对应数据节点做 操作。数据节点在自己的节点中建立行压缩表的空表，待之后生成列压缩表后再 作填写。

如图4，通过字段数，启动相应个数的单列DS，在源数据库中按列切分，读 出其中一列的全部数据。

如图5，单列DS中进行全列排序，rowkey根据排序列的顺序调整，形成倒 排索引。排序过后，可以形成该列的全局字典。原始列需保留。

如图6，单列DS建立全列数据的组合索引，得到以下三个向量。

如图7，形成字典后，单列DS进行以下的工作：

对以rowkey排序的原始列开始做字典替换，形成处理后的数据。

向IS请求rowkey的数据分布索引，并依据索引来切分处理后的数据。

将切片后的数据成组发往对应CS，让该CS填行压缩表，之后丢弃原始列。 单列DS先对字典进行均分，再依据字典对处理后的向量切片，同时将Index Offset向量和RowKey向量都切成对应份数，成为局部向量。切片后可以确定 每个切片的ceiling和floor，也就可以形成该列的数据分布索引了。

如图9，单列DS将生成的数据分布索引发送给IS。

如图10，按照之前切片的原则，启动或选择对应的CS。

如图11，DS将生成的切片数据以及对应的局部三向量，分别发送给CS。

所有DS做完后，CS中的行压缩表子表填写完成，请参考图12。

结束流程，结束后数据和索引情况如图13和图14。

按照上述步骤，便可很好地实现本发明。

上述本申请实施例中的技术方案，至少具有如下的技术效果或优点：

由于采用了字典压缩以及位压缩技术手段，利用字典压缩对重复数据进行去 重处理，避免存储多余的冗余数据，在存储列压缩索引频数向量和行号索引向量 中采用位压缩手段，充分利用物理内存，显著提高内存存储的利用率，所以，有 效解决了现有的分布式内存数据库系统索引存在存储索引效率较低，利用索引查 询数据速度较慢，占用内存较多的技术问题，进而实现了能够高效的存储索引， 能够利用索引快速查询数据，对索引进行压缩处理，降低了内存需求的技术效果。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本 创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意 欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明 的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等 同技术的范围之内，则本发明也意图包含这些改动和变型在内。