关系型数据库的存储方法及装置转让专利
申请号 : CN201110056705.1
文献号 : CN102129458B
文献日 : 2012-12-12
发明人 : 胡劲松
申请人 : 北京翰云时代科技有限公司
摘要 :
本发明公开一种关系型数据库的存储方法及装置，包括：建立控制表，用以存储表段的信息，包括表段的标识和表段所存储记录的最小及最大主键值；当有新的记录插入表时，将新的记录插入该表表段的内存表，并在该表段的信息改变时，在控制表中进行相应更新；当有表段的内存表中所有记录所占用内存达到预定义的上限时，将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，并清空该表段的内存表。采用本发明可以实现关系型数据库自动分段并按列存储，并节省存储时的开销，且本发明的关系型数据库的存储结构适合于作为关系型数据库的存储基础。
权利要求 :
1.一种关系型数据库的存储方法，其特征在于，包括：
建立控制表，用以存储表段的标识和表段所存储记录的最小及最大主键值，并按表段最小主键值排序；
当有新的记录插入关系型数据库的表时：
若关系型数据库的表中没有记录，则新建该表的表段，将新的记录插入该表段的内存表，将该表段的标识存储至控制表，将新的记录的主键值作为该表段所存储记录的最小及最大主键值存储至控制表；
若关系型数据库的表中已有记录，则根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，查找新的记录应插入的表段，将新的记录插入该表段的内存表，插入时按主键值排序；若插入改变了该表段所存储记录的最小或最大主键值，则在控制表中进行相应更新；
当有表段的内存表中所有记录所占用内存达到预定义的上限时：
将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，并清空该表段的内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表段数据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
2.如权利要求1所述的方法，其特征在于，所述根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，确定新的记录应插入的表段，包括：根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，采用二分法查找新的记录应插入的表段：若新的记录的主键值介于两个表段的最小主键值之间，则将前一个表段作为新的记录应插入的表段；
若新的记录的主键值在第一个表段的最小主键值之前，则将第一个表段作为新的记录应插入的表段；
若新的记录的主键值在最后一个表段的最小主键值之后，则将最后一个表段作为新的记录应插入的表段。
3.如权利要求1所述的方法，其特征在于，表段数据文件中所存储的数据包括记录对应的列值数据和元数据；其中：每个列的列值数据个数相等；每个列的列值数据按固定的列值数据个数划分为数据块，形成列值数据块；
元数据存储于元数据块中；元数据记录每个列值数据块在表段数据文件中的位置、表段数据文件中的记录个数和元数据块在表段数据文件中的位置。
4.如权利要求3所述的方法，其特征在于，表段数据文件中列值数据和元数据的存储次序为：第一个列的列值数据、第二个列的列值数据直至最后一个列的列值数据、以及元数据。
5.如权利要求3所述的方法，其特征在于，元数据缓存于内存中。
6.如权利要求1所述的方法，其特征在于，还包括：
当有表段所存储的所有记录数目达到预定义的上限时：
将部分记录保留在该表段中，并新建表段，将其余记录存储至新建的表段；
若该表段所存储记录的最小或最大主键值发生改变，则在控制表中进行相应更新；
在控制表中新增新建表段的标识及所存储记录的最小及最大主键值，插入时按最小主键值排序。
7.如权利要求6所述的方法，其特征在于，所述将部分记录保留在该表段中，并新建表段，将其余记录存储至新建的表段，包括：将前一半记录保留在该表段中，并新建表段，将后一半记录存储至新建的表段。
8.一种关系型数据库的存储装置，其特征在于，包括：
控制表建立模块，用于建立控制表，用以存储表段的标识和表段所存储记录的最小及最大主键值，并按表段最小主键值排序；
表段建立模块，用于当有新的记录插入关系型数据库的表时：若关系型数据库的表中没有记录，则新建该表的表段；第一记录插入模块，用于将新的记录插入该新建的表段的内存表；第一控制表更新模块，用于将该新建的表段的标识存储至控制表，将新的记录的主键值作为该新建的表段所存储记录的最小及最大主键值存储至控制表；
表段查找模块，用于当有新的记录插入关系型数据库的表时：若关系型数据库的表中已有记录，则根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，查找新的记录应插入的表段；第二记录插入模块，用于将新的记录插入该查找的表段的内存表，插入时按主键值排序；第二控制表更新模块，用于若插入改变了该查找的表段所存储记录的最小或最大主键值，则在控制表中进行相应更新；
记录转存处理模块，用于当有表段的内存表中所有记录所占用内存达到预定义的上限时：将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，并清空该表段的内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表段数据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
9.如权利要求8所述的装置，其特征在于，所述表段查找模块具体用于：根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，采用二分法查找新的记录应插入的表段：若新的记录的主键值介于两个表段的最小主键值之间，则将前一个表段作为新的记录应插入的表段；
若新的记录的主键值在第一个表段的最小主键值之前，则将第一个表段作为新的记录应插入的表段；
若新的记录的主键值在最后一个表段的最小主键值之后，则将最后一个表段作为新的记录应插入的表段。
10.如权利要求8所述的装置，其特征在于，表段数据文件中所存储的数据包括记录对应的列值数据和元数据；其中：每个列的列值数据个数相等；每个列的列值数据按固定的列值数据个数划分为数据块，形成列值数据块；
元数据存储于元数据块中；元数据记录每个列值数据块在表段数据文件中的位置、表段数据文件中的记录个数和元数据块在表段数据文件中的位置。
11.如权利要求10所述的装置，其特征在于，表段数据文件中列值数据和元数据的存储次序为：第一个列的列值数据、第二个列的列值数据直至最后一个列的列值数据、以及元数据。
12.如权利要求10所述的装置，其特征在于，元数据缓存于内存中。
13.如权利要求8所述的装置，其特征在于，还包括：
表段拆分模块，用于当有表段所存储的所有记录数目达到预定义的上限时：将部分记录保留在该表段中，并新建表段，将其余记录存储至新建的表段；
第三控制更新模块，用于若该表段所存储记录的最小或最大主键值发生改变，则在控制表中进行相应更新；在控制表中新增新建表段的标识及所存储记录的最小及最大主键值，插入时按最小主键值排序。
14.如权利要求13所述的装置，其特征在于，所述表段拆分模块具体用于：将前一半记录保留在该表段中，并新建表段，将后一半记录存储至新建的表段。
说明书 :
关系型数据库的存储方法及装置
技术领域
[0001] 本发明涉及数据库技术领域，尤其涉及关系型数据库的存储方法及装置。
背景技术
[0002] 现有技术提供了多种实现数据库存储的方法。
[0003] 例如，现有技术一提供一种行存储数据库的方法，如Oracle（Oracle DatabaseConcepts）等方法。该方法按照先入先存储的规则对关系型数据库的记录按行进行存储，并对主键建立B+树等类型的唯一性索引。但是，现有技术一存在如下不足：首先主键索引占
有一定的存储空间，增加了系统开销，尽管某些现有的数据库采取了按列分区的机制来提
高某些查询性能，但这又提高了检查主键是否唯一的开销，因为，系统不得不检查所有分区中主键的唯一性，分区越多，检查的开销越大；其次由于按行存储，所有的列存储在一起，不能按需读取列，读取部分列不得不先读取全部列然后过滤掉不需要的列，这样就增加了硬
盘IO，降低了性能。
有一定的存储空间，增加了系统开销，尽管某些现有的数据库采取了按列分区的机制来提
高某些查询性能，但这又提高了检查主键是否唯一的开销，因为，系统不得不检查所有分区中主键的唯一性，分区越多，检查的开销越大；其次由于按行存储，所有的列存储在一起，不能按需读取列，读取部分列不得不先读取全部列然后过滤掉不需要的列，这样就增加了硬
盘IO，降低了性能。
[0004] 现有技术二提供一种实现基于列存储的关系型数据库的方法及装置（申请号/专利号：200810187227）。但是，尽管现有技术二解决了行存储数据库不能按需读取列的问题，但是仍存在如下缺陷：插入记录时，按列分开存储，并且每个列的值按排序存储，增加了存储时的开销；由于将列分开存储，需要连接数据把列连在一起来重构原始的记录，维护连接数据还增加了系统的负担。
[0005] 现有 技 术 三 提供 一 种MonetDB列 存 储数 据 库（P.A.Boncz.：“Monet:A Next-Generation DBMS Kernel For Query-Intensive Applications”）。现有技术三的MonetDB虽然也是按列存储的数据库系统，它也有列数据库的按需读取列的优点，但是，仍存在如下缺陷：存储每个列时需要存储记录的ROWID，系统需要通过ROWID来连接列值从而
重建记录，且ROWID通常是长整形或者更长的类型，这样增加了系统的开销。
重建记录，且ROWID通常是长整形或者更长的类型，这样增加了系统的开销。
[0006] 现有技术四提供一种Google BigTable（Fay Chang等：Bigtable:A Distributed Storage System for Structured Data）。尽管Google BigTable是按RowKey排序及分段来存储记录，但是，它引入了列族（即Column Family）的概念，即一条记录由一个或多个列族组成，存储时按列族存储，每个列族对应一个数据文件（即Google SSTable文件），这样，一个表段（Tablet）就会对应一个或多个数据文件（SSTable文件），而且，它在列族中存储的值都是Key/Value形式，不适合用于存储关系型数据。事实上，BigTable是一个多维的
分布式的映射表的存储系统，这种存储结构不适合作为关系型数据库的存储基础。
分布式的映射表的存储系统，这种存储结构不适合作为关系型数据库的存储基础。
发明内容
[0007] 本发明实施例提供一种关系型数据库的存储方法，用以实现关系型数据库的自动分段并按列存储，并节省存储时的开销，且存储结构适合于作为关系型数据库的存储基础，该方法包括：
[0008] 建立控制表，用以存储表段的标识和表段所存储记录的最小及最大主键值，并按表段最小主键值排序；
[0009] 当有新的记录插入关系型数据库的表时：
[0010] 若关系型数据库的表中没有记录，则新建该表的表段，将新的记录插入该表段的内存表，将该表段的标识存储至控制表，将新的记录的主键值作为该表段所存储记录的最
小及最大主键值存储至控制表；
小及最大主键值存储至控制表；
[0011] 若关系型数据库的表中已有记录，则根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，查找新的记录应插入的表段，将新的记录插入该表段的内存表，插入时按主键值排序；若插入改变了该表段所存储记录的最小或最大主键值，则在控制表
中进行相应更新；
中进行相应更新；
[0012] 当有表段的内存表中所有记录所占用内存达到预定义的上限时：
[0013] 将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，并清空该表段的内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表段数
据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
[0014] 本发明实施例还提供一种关系型数据库的存储装置，用以实现关系型数据库的自动分段并按列存储，并节省存储时的开销，且存储结构适合于作为关系型数据库的存储基
础，该装置包括：
础，该装置包括：
[0015] 控制表建立模块，用于建立控制表，用以存储表段的标识和表段所存储记录的最小及最大主键值，并按表段最小主键值排序；
[0016] 表段建立模块，用于当有新的记录插入关系型数据库的表时：若关系型数据库的表中没有记录，则新建该表的表段；第一记录插入模块，用于将新的记录插入该新建的表段的内存表；第一控制表更新模块，用于将该新建的表段的标识存储至控制表，将新的记录的主键值作为该新建的表段所存储记录的最小及最大主键值存储至控制表；
[0017] 表段查找模块，用于当有新的记录插入关系型数据库的表时：若关系型数据库的表中已有记录，则根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，
查找新的记录应插入的表段；第二记录插入模块，用于将新的记录插入该查找的表段的内
存表，插入时按主键值排序；第二控制表更新模块，用于若插入改变了该查找的表段所存储记录的最小或最大主键值，则在控制表中进行相应更新；
查找新的记录应插入的表段；第二记录插入模块，用于将新的记录插入该查找的表段的内
存表，插入时按主键值排序；第二控制表更新模块，用于若插入改变了该查找的表段所存储记录的最小或最大主键值，则在控制表中进行相应更新；
[0018] 记录转存处理模块，用于当有表段的内存表中所有记录所占用内存达到预定义的上限时：将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，并清
空该表段的内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表段数
据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
空该表段的内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表段数
据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
[0019] 本发明实施例与现有技术一相比，无需对主键建立索引，可节省存储时的开销；且本发明实施例按列存储，可解决行存储数据库不能按需读取列的问题；
[0020] 本发明实施例将表分段并按主键值对记录进行排序，与现有技术二相比可降低存储时的开销；且不同于现有技术二需要连接数据将分开存储的列连在一起重构原始记录，
本发明实施例无需连接数据来重构记录，不会增加维护连接数据的负担；
本发明实施例无需连接数据来重构记录，不会增加维护连接数据的负担；
[0021] 同样的，不同于现有技术三需要ROWID连接列值从而重建记录，本发明实施例无需存储记录的ROWID来重建记录，不会增加存储时的负担；
[0022] 与现有技术四相比，本发明实施例中的表段只对应一个数据文件，而且存储的是关系型数据库的记录，并不是Key/Value形式的数据，存储时本发明实施例是按记录的列
存储，没有列族的概念，完全适合作为关系型数据库的存储基础。
存储，没有列族的概念，完全适合作为关系型数据库的存储基础。
[0023] 本发明实施例可以提高关系型数据库的查询性能，且基于主键排序及分段来实现关系型数据库的存储，可以作为实现关系型数据库的并行计算的基本存储方式，将分段存
储的表数据均衡分配到并行数据库的节点中，再利用Map/Reduce算法实施并行运算。
储的表数据均衡分配到并行数据库的节点中，再利用Map/Reduce算法实施并行运算。
附图说明
[0024] 为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其
他的附图。在附图中：
他的附图。在附图中：
[0025] 图1为本发明实施例中关系型数据库的存储方法的流程图；
[0026] 图2为本发明实施例中控制表的结构示意图；
[0027] 图3为本发明实施例中插入记录到一个空表中的示意图；
[0028] 图4为本发明实施例中插入记录到非空表中情形一的示意图；
[0029] 图5为本发明实施例中插入记录到非空表中情形二的示意图；
[0030] 图6为本发明实施例中插入记录导致表段的内存表中记录所占用的内存达到上限的示意图；
[0031] 图7为本发明实施例中表示表段数据文件的格式示意图；
[0032] 图8为本发明实施例中表示表段分裂的示意图；
[0033] 图9为本发明实施例中一个投影查询的示意图；
[0034] 图10为本发明实施例中一个条件查询的示意图；
[0035] 图11为本发明实施例中一个并行数据库分配表段数据的示意图；
[0036] 图12为本发明实施例中关系型数据库的存储装置的结构图。
具体实施方式
[0037] 为使本发明实施例的目的、技术方案和优点更加清楚明白，下面结合附图对本发明实施例做进一步详细说明。在此，本发明的示意性实施例及其说明用于解释本发明，但并不作为对本发明的限定。
[0038] 如图1所示，本发明实施例中关系型数据库的存储方法流程可以包括：
[0039] 先执行步骤101：建立控制表，用以存储表段的标识和表段所存储记录的最小及最大主键值，并按表段最小主键值排序；
[0040] 当有新的记录插入表时：
[0041] 若表中没有记录，则执行步骤102：新建该表的表段，将新的记录插入该表段的内存表；接着执行步骤103：将该表段的标识存储至控制表，将新的记录的主键值作为该表段所存储记录的最小及最大主键值存储至控制表；
[0042] 若表中已有记录，则执行步骤104：根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，查找新的记录应插入的表段，将新的记录插入该表段的内存表，插入时按主键值排序；若插入改变了该表段所存储记录的最小或最大主键值，则还需执行
步骤105：在控制表中进行相应更新；
步骤105：在控制表中进行相应更新；
[0043] 当有表段的内存表中所有记录所占用内存达到预定义的上限时：
[0044] 执行步骤106：将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，存储记录时按列存储，且保持按主键值排序；接着执行步骤107：清空该表段的内存表；其中在执行步骤106时，若硬盘上没有该表段数据文件，则还包括：新建该表段数据文件（步骤106a）；若硬盘上已有该表段数据文件，则还包括：在存储时将内存表中的记录与该表段数据文件中已有的记录合并（步骤106b）。
[0045] 下面对图1所示流程作如下详细说明：
[0046] 本发明实施例中，关系型数据库中的表被分成段称之为表段，每个表段中的记录数有一个上限。表段由内存表和表段数据文件组成。内存表是表段中常驻内存的数据结
构，用以存储新插入的记录，并按记录的主键值排序，所存储的记录占用的内存不能超过预定义的上限，否则需要将记录存储到表段数据文件中，然后清空内存表。表段数据文件用以存储表段的记录，按列存储，并且按记录的主键值排序。控制表用以管理表段，存储每个表段的信息，包括表段的标识和表段所存储记录的最小及最大主键值。控制表所存储的表段
信息可以按表段所存储的最小主键值排序。
构，用以存储新插入的记录，并按记录的主键值排序，所存储的记录占用的内存不能超过预定义的上限，否则需要将记录存储到表段数据文件中，然后清空内存表。表段数据文件用以存储表段的记录，按列存储，并且按记录的主键值排序。控制表用以管理表段，存储每个表段的信息，包括表段的标识和表段所存储记录的最小及最大主键值。控制表所存储的表段
信息可以按表段所存储的最小主键值排序。
[0047] 具体实施时，首先建立控制表，用以存储表段的信息，包括表段的标识（ID）和表段所存储记录的最小及最大主键值。
[0048] 例如，图2为本发明实施例中控制表的结构示意图。如图2所示，控制表中包括表段的标识（TABLET_ID），表段所存储记录的最小主键值（MIN_PK）及最大主键值（MAX_PK）。
在没有记录插入表时，控制表为空。
在没有记录插入表时，控制表为空。
[0049] 具体实施时，当有新的记录插入表时，分成两种情况：
[0050] 一是表中没有记录，此时控制表为空，需要新建该表的表段，将新的记录插入该表段的内存表中，将该表段的信息存储到控制表中，具体包括将该表段的标识存储至控制表，将新的记录的主键值作为该表段所存储记录的最小及最大主键值存储至控制表。由于表段中只有一条记录，表段所存储记录的最小和最大主键值为插入记录的主键值。
[0051] 例如，图3为本发明实施例中插入记录到一个空表中的示意图。如图3所示，本例中表的结构为（ID，NAME），插入的记录为（1001,中国），表段的内存表中插入了记录（1001,中国），控制表中插入了新的表段信息：（1,1001,1001），即表段的ID为1，表段所存储记录的最小主键值为1001，而存储的最大主键值也为1001。
[0052] 二是表中已有记录，此时控制表不为空，需要根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，查找新的记录应插入的表段，然后，在查找到的表段的内存表中插入新的记录，插入时按主键值排序。如果插入的记录改变了该表段所存储记录
的最小或最大主键值，则需要更新控制表中对应表段的信息。其中，在查找新的记录应插入的表段时，可以根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，采
用二分法进行查找。
的最小或最大主键值，则需要更新控制表中对应表段的信息。其中，在查找新的记录应插入的表段时，可以根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，采
用二分法进行查找。
[0053] 之所以用二分法查找的原因是由于在实际应用中会有成百上千乃至上万个表段，为了提高性能，用二分法查找，由于控制表中存储的表段信息是按最小主键值排序，查找插入的目标表段可根据插入记录的主键值以及所有表段的最小主键值用二分法查找定位：
[0054] 当有新的记录插入表时，若新的记录的主键值介于两个表段的最小主键值之间，则将前一个表段作为新的记录应插入的表段；若新的记录的主键值在第一个表段的最小主
键值之前，则将第一个表段作为新的记录应插入的表段；若新的记录的主键值在最后一个
表段的最小主键值之后，则将最后一个表段作为新的记录应插入的表段。
键值之前，则将第一个表段作为新的记录应插入的表段；若新的记录的主键值在最后一个
表段的最小主键值之后，则将最后一个表段作为新的记录应插入的表段。
[0055] 例如，图4为本发明实施例中插入记录到非空表中控制表无变化的示意图。如图4所示，控制表中有两个表段：（1，1001，1005）和（2，1010，1011），其中表段1中有记录：
（1001，中国），（1005，韩国)，表段2中有记录：（1010，美国），（1011，加拿大）。插入记录（1003,日本），控制表中所有表段所存储记录的最小主键值从小到大为：1001，1010，二分法查找的结果是表段1（由于表段1和2的最小主键值从小到大为1001、1010，这样当存储主
键值为1003的记录时，由于1003大于1001而小于1010，所以应插入表段1），所以在表段
1中插入记录（1003，日本），表段1的内存表中插入了（1003，日本），按照主键值次序，依次为：（1001，中国），（1003，日本），（1005，韩国），由于记录被插入在表段的中间，表段所存储记录的最小和最大主键值没有发生变化，因此无需改变控制表中该表段的信息。
（1001，中国），（1005，韩国)，表段2中有记录：（1010，美国），（1011，加拿大）。插入记录（1003,日本），控制表中所有表段所存储记录的最小主键值从小到大为：1001，1010，二分法查找的结果是表段1（由于表段1和2的最小主键值从小到大为1001、1010，这样当存储主
键值为1003的记录时，由于1003大于1001而小于1010，所以应插入表段1），所以在表段
1中插入记录（1003，日本），表段1的内存表中插入了（1003，日本），按照主键值次序，依次为：（1001，中国），（1003，日本），（1005，韩国），由于记录被插入在表段的中间，表段所存储记录的最小和最大主键值没有发生变化，因此无需改变控制表中该表段的信息。
[0056] 又如，图5为本发明实施例中插入记录到非空表中引起控制表变化的示意图。如图5所示，控制表中有两个表段：（1，1001，1005）和（2，1010，1011），其中表段1中有记录：（1001，中国），（1005，韩国），表段2中有记录：（1010，美国），（1011，加拿大）。插入记录（1006，印度），控制表中所有表段所存储记录的最小主键值为：1001，1010，二分法查找的结果是表段1（由于表段1和2的最小主键值从小到大为1001、1010，这样当存储主
键值为1006的记录时，由于1006大于1001而小于1010，所以应插入表段1），所以在表
段1中插入记录（1006，印度），表段1的内存表中插入了（1006，印度），按照主键值次序，依次为：（1001，中国），（1005，韩国），（1006，印度）。由于记录被插入到表段的最后，表段所存储记录的最大主键值发生了变化，更新控制表中的第一个表段的最大主键值为1006：
（1,1001,1006）。
键值为1006的记录时，由于1006大于1001而小于1010，所以应插入表段1），所以在表
段1中插入记录（1006，印度），表段1的内存表中插入了（1006，印度），按照主键值次序，依次为：（1001，中国），（1005，韩国），（1006，印度）。由于记录被插入到表段的最后，表段所存储记录的最大主键值发生了变化，更新控制表中的第一个表段的最大主键值为1006：
（1,1001,1006）。
[0057] 具体实施时，当有表段的内存表中所有记录所占用内存达到预定义的上限时：
[0058] 将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，然后将内存表清空以减少内存的使用，该操作可称之为紧缩内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表段数据文件，则新建该表段数据文件；若硬盘上已有
该表段数据文件，表明以前做过紧缩内存表的操作，则在存储时将内存表中的记录与该表
段数据文件中已有的记录合并，仍按列存储，并保持按主键值排序。
该表段数据文件，表明以前做过紧缩内存表的操作，则在存储时将内存表中的记录与该表
段数据文件中已有的记录合并，仍按列存储，并保持按主键值排序。
[0059] 例如，图6为本发明实施例中插入记录导致表段的内存表中记录所占用的内存达到上限的示意图。如图6所示，表段的内存表中有记录（1001，中国），（1003，日本），（1005，韩国），表段的表段数据文件中存储有记录（1002，越南），（1006，印度）。插入记录（1004，马来西亚）导致内存表所占内存达到预定义的上限，例如：假设ID是整数类型，NAME是字符类型，整数所占内存是4个字节，每个中文字符占2个字节，那么，插入（1004，马来西亚）到内存表后内存表中的记录为：（1001，中国），（1003，日本），（1004，马来西亚），（1005，韩国），内存表所占的内存应为：（4+2×2）＋（4＋2×2）＋（4＋2×4）＋（4＋2×2）＝36，假设预
定义的内存上限为32，那么内存表所占的内存达到上限。将内存表中的记录和表段数据文
件中已有记录合并存储，保持主键值的排序，（1001,1002,1003,1004,1005,1006），对应的名称列值为：（中国，越南，日本，马来西亚，韩国，印度），表段的内存表被清空。
定义的内存上限为32，那么内存表所占的内存达到上限。将内存表中的记录和表段数据文
件中已有记录合并存储，保持主键值的排序，（1001,1002,1003,1004,1005,1006），对应的名称列值为：（中国，越南，日本，马来西亚，韩国，印度），表段的内存表被清空。
[0060] 具体实施时，表段数据文件中所存储的数据可以包括：
[0061] 记录对应的列值数据和元数据；列值数据是记录的组成部分，比如有ID列值数据和NAME列值数据，所有的列值数据组合在一起构成记录。存储时，ID列值数据和NAME列
值数据分开存储。
值数据分开存储。
[0062] 其中：
[0063] 每个列的列值数据个数相等；由于记录的个数决定列值数据个数，所以它们必然相等。比如：有记录（1001，中国），（1002，美国），记录数为2，按列存储：ID：1001，1002；
NAME：中国，美国；每个列的列值数据个数为2，都等于记录的个数2；
NAME：中国，美国；每个列的列值数据个数为2，都等于记录的个数2；
[0064] 每个列的列值数据按固定的列值数据个数划分为数据块，形成列值数据块；
[0065] 元数据存储于元数据块中；元数据记录每个列值数据块在表段数据文件中的位置、表段数据文件中的记录个数和元数据块在表段数据文件中的位置。记录个数＝每个列
值数据的个数，而不是所有的列值数据个数，比如：有记录：（1001，中国），（1002，美国），按列存储时，ID：1001，1002；NAME：中国，美国；记录数为2，每个列值数据的个数也为2，所有的列值数据个数加起来为4。
值数据的个数，而不是所有的列值数据个数，比如：有记录：（1001，中国），（1002，美国），按列存储时，ID：1001，1002；NAME：中国，美国；记录数为2，每个列值数据的个数也为2，所有的列值数据个数加起来为4。
[0066] 具体实施时，表段数据文件中列值数据和元数据的存储次序可以是：
[0067] 第一个列的列值数据、第二个列的列值数据直至最后一个列的列值数据、以及元数据。
[0068] 元数据记录的列值数据块在表段数据文件中的位置可以在按列存储列值数据时获得，元数据块在表段数据文件中的位置是紧接最后一个列的最后一个列值数据块。由于
元数据通常很小，可以在内存中缓存一份拷贝以加快访问速度。
元数据通常很小，可以在内存中缓存一份拷贝以加快访问速度。
[0069] 例如，图7为本发明实施例中表段数据文件的格式示意图。如图7所示，存储记录为：（1001，中国），（1002，越南），（1003，日本），（1004，马来西亚），（1005，韩国）和（1006，印度）。划分列值数据成列值数据块的列值数据个数为2，第一个列的列值数据块共有三个，分别为：（1001，1002），（1003，1004）,（1005，1006），第二个列的列值数据块共有三个，分别为：（中国，越南），（日本，马来西亚），（韩国，印度），元数据块为：（0，8，16，32，48，68，6，84），其中，0为列值数据块（1001，1002）在表段数据文件中的位置，8为列值数据块（1003，1004）在表段数据文件中的位置，16为列值数据块（1005，1006）在表段数据文件中的位置，32为列值数据块（中国，越南）在表段数据文件中的位置，48为列值数据块（日本，马来西亚）在表段数据文件中的位置，68为列值数据块（韩国，印度）在表段数据文件中的位置，6为记录个数，84为元数据块在表段数据文件中的位置。
[0070] 具体实施时，当有表段所存储的所有记录数目达到预定义的上限时：将部分记录保留在该表段中，并新建表段，将其余记录存储至新建的表段；例如，将前一半记录保留在该表段中，并新建表段，将后一半记录存储至新建的表段。由于该表段的最大主键值发生变化，在控制表中更新该表段的最大主键值；在控制表中新增新建表段的标识及所存储记录
的最小及最大主键值，插入时按表段最小主键值排序。
的最小及最大主键值，插入时按表段最小主键值排序。
[0071] 例如，图8为本发明实施例中表段分裂的示意图。如图8所示，表段中存储记录为：（1001，中国），（1002，越南），（1003，日本），（1004，马来西亚），（1005，韩国）和（1006，印度），插入记录（1007，中国香港）导致表段达到表段的最大记录数7，对表段进行分裂，变成两个表段：表段1（1，1001，1004）和表段2（2，1005，1007），其中表段1存储的记录为：（1001，中国），（1002，越南），（1003，日本），（1004，马来西亚），而表段2存储的记录为：（1005，韩国），（1006，印度），（1007，中国香港），控制表中表段1的最大主键值从1006改为1004，并新增加表段2的信息：表段标识为2，最小主键值为1005，最大主键值为1007。
[0072] 下面简单介绍按本发明实施例方法存储的关系型数据库的一些基本的数据库查询操作。
[0073] 一、投影查询
[0074] 投影查询是指查询表中记录的某些列，由于本发明实施例是按列存储记录，这样就可以按需读取列，而不同于行存储的数据库那样需要读取所有列的数据，这样就大大减
少了硬盘输入输出，从而提高了关系型数据库的查询性能。
少了硬盘输入输出，从而提高了关系型数据库的查询性能。
[0075] 例如，图9为本发明实施例中一个投影查询的示意图。如图9所示，投影查询语句是：“SELECT NAME FROM COUNTRY”，由于本发明实施例按列存储记录数据，可以只读入列NAME的数据，输出结果，而列ID的值数据没有被读取，从而提高了查询性能。
[0076] 二、条件查询
[0077] 条件查询是指查询语句有查询条件，由于本发明实施例是按列存储记录，可以根据查询条件读取相关的列的记录，一旦记录的列值通过了这些查询条件，所有其他需要输
出的列值就被读取，输出到最终的结果当中，这样比行数据库减少了IO。
出的列值就被读取，输出到最终的结果当中，这样比行数据库减少了IO。
[0078] 例如，图10为本发明实施例中一个条件查询的示意图。如图10所示，条件查询的语句是：“SELECT ID FROM COUNTRY WHERE NAME=‘韩国”’，查询时可首先利扫描列NAME的值数据查到第五个记录满足条件，这样读取第五个记录的列ID的值，由于本发明实施例中
每个列值数据块中存取有固定数目的列值数据，如图10中每个列值数据块存取的列值数
据个数为2，这样可以计算得到符合条件的ID值在第三个数据块中，然后，可以利用元数据中存储的列值数据块的位置数据快速定位列ID第三个数据块，从而读取符合条件的ID值，
即1005。
每个列值数据块中存取有固定数目的列值数据，如图10中每个列值数据块存取的列值数
据个数为2，这样可以计算得到符合条件的ID值在第三个数据块中，然后，可以利用元数据中存储的列值数据块的位置数据快速定位列ID第三个数据块，从而读取符合条件的ID值，
即1005。
[0079] 三、并行处理
[0080] 由于本发明实施例中的表被分成表段，这样，如果在一个集群及云计算的环境中，由于有多个服务器的存在，可以将表段均匀分配给每一个服务器，查询表中的记录时，集群中的服务器就可以同时展开运算，各自处理自己硬盘中的记录数据，达到并行处理的目的，这就能大大提高数据库的性能。
[0081] 例如，图11为本发明实施例中一个集群数据库并行处理的示意图。如图11所示，集群数据库由两个服务器组成，表由两个表段组成，分别存储在两个服务器中，每个服务器提供有关表段的记录查询服务。
[0082] 本发明实施例中还提供了一种关系型数据库的存储装置，如下面的实施例所述。由于该装置解决问题的原理与关系型数据库的存储方法相似，因此该装置的实施可以参见
关系型数据库的存储方法的实施，重复之处不再赘述。
关系型数据库的存储方法的实施，重复之处不再赘述。
[0083] 如图12所示，本发明实施例中关系型数据库的存储装置可以包括：
[0084] 控制表建立模块1201，用于建立控制表，用以存储表段的标识和表段所存储记录的最小及最大主键值，并按表段最小主键值排序；
[0085] 表段建立模块1202，用于当有新的记录插入表时：若表中没有记录，则新建该表的表段；第一记录插入模块1203，用于将新的记录插入该新建的表段的内存表；第一控制
表更新模块1204，用于将该新建的表段的标识存储至控制表，将新的记录的主键值作为该
新建的表段所存储记录的最小及最大主键值存储至控制表；
表更新模块1204，用于将该新建的表段的标识存储至控制表，将新的记录的主键值作为该
新建的表段所存储记录的最小及最大主键值存储至控制表；
[0086] 表段查找模块1205，用于当有新的记录插入表时：若表中已有记录，则根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，查找新的记录应插入的表
段；第二记录插入模块1206，用于将新的记录插入该查找的表段的内存表，插入时按主键
值排序；第二控制表更新模块1207，用于若插入改变了该查找的表段所存储记录的最小或
最大主键值，则在控制表中进行相应更新；
段；第二记录插入模块1206，用于将新的记录插入该查找的表段的内存表，插入时按主键
值排序；第二控制表更新模块1207，用于若插入改变了该查找的表段所存储记录的最小或
最大主键值，则在控制表中进行相应更新；
[0087] 记录转存处理模块1208，用于当有表段的内存表中所有记录所占用内存达到预定义的上限时：将该表段内存表中所有记录存储至硬盘上该表段对应的一个表段数据文件，
并清空该表段的内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表
段数据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
并清空该表段的内存表；存储记录时按列存储，且保持按主键值排序；若硬盘上没有该表
段数据文件，则新建该表段数据文件；若硬盘上已有该表段数据文件，则在存储时将内存表中的记录与该表段数据文件中已有的记录合并。
[0088] 一个实施例中，表段查找模块1205具体可以用于：根据新的记录的主键值及控制表中所有表段所存储记录的最小主键值，采用二分法查找新的记录应插入的表段：
[0089] 若新的记录的主键值介于两个表段的最小主键值之间，则将前一个表段作为新的记录应插入的表段；
[0090] 若新的记录的主键值在第一个表段的最小主键值之前，则将第一个表段作为新的记录应插入的表段；
[0091] 若新的记录的主键值在最后一个表段的最小主键值之后，则将最后一个表段作为新的记录应插入的表段。
[0092] 一个实施例中，表段数据文件中所存储的数据包括记录对应的列值数据和元数据；其中：
[0093] 每个列的列值数据个数相等；每个列的列值数据按固定的列值数据个数划分为数据块，形成列值数据块；
[0094] 元数据存储于元数据块中；元数据记录每个列值数据块在表段数据文件中的位置、表段数据文件中的记录个数和元数据块在表段数据文件中的位置。
[0095] 一个实施例中，表段数据文件中列值数据和元数据的存储次序为：
[0096] 第一个列的列值数据、第二个列的列值数据直至最后一个列的列值数据、以及元数据。
[0097] 一个实施例中，元数据缓存于内存中。
[0098] 一个实施例中，图12所示的关系型数据库的存储装置还可以包括：
[0099] 表段拆分模块，用于当有表段所存储的所有记录数目达到预定义的上限时：将部分记录保留在该表段中，并新建表段，将其余记录存储至新建的表段；
[0100] 第三控制更新模块，用于若该表段所存储记录的最小或最大主键值发生改变，则在控制表中进行相应更新；在控制表中新增新建表段的标识及所存储记录的最小及最大主
键值，插入时按表段最小主键值排序。
键值，插入时按表段最小主键值排序。
[0101] 一个实施例中，表段拆分模块具体可以用于：将前一半记录保留在该表段中，并新建表段，将后一半记录存储至新建的表段。
[0102] 本发明实施例与现有技术一相比，无需对主键建立索引，可节省系统开销；且本发明实施例按列存储，可解决行存储数据库不能按需读取列的问题；
[0103] 本发明实施例将表分段并按主键值对记录进行排序，与现有技术二相比可降低存储时的开销；且不同于现有技术二需要连接数据将分开存储的列连在一起重构原始记录，
本发明实施例无需连接数据来重构记录，不会增加维护连接数据的系统负担；
本发明实施例无需连接数据来重构记录，不会增加维护连接数据的系统负担；
[0104] 同样的，不同于现有技术三需要ROWID连接列值从而重建记录，本发明实施例无需存储记录的ROWID来重建记录，不会增加系统负担；
[0105] 与现有技术四相比，本发明实施例中的表段只对应一个数据文件，而且存储的是关系型数据库的记录，并不是Key/Value形式的数据，存储时本发明实施例是按记录的列
存储，没有列族的概念，完全适合作为关系型数据库的存储基础。
存储，没有列族的概念，完全适合作为关系型数据库的存储基础。
[0106] 本发明实施例可以提高数据库的查询性能，且基于主键排序及分段来实现关系型数据库的存储，可以作为实现关系型数据库的并行计算的基本存储方式，将分段存储的表
数据均衡分配到并行数据库的节点中，再利用Map/Reduce算法实施并行运算。
数据均衡分配到并行数据库的节点中，再利用Map/Reduce算法实施并行运算。
[0107] 本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质（包括但不限于磁盘存储器、CD-ROM、光学存储器等）上实施的计算机程序产品的形式。
[0108] 本发明是参照根据本发明实施例的方法、设备（系统）、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算
机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理
器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生
用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能
的装置。
机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理
器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生
用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能
的装置。
[0109] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指
令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或
多个方框中指定的功能。
令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或
多个方框中指定的功能。
[0110] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或
其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图
一个方框或多个方框中指定的功能的步骤。
其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图
一个方框或多个方框中指定的功能的步骤。
[0111] 以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。