论文部分内容阅读
摘 要： 以内存数据库数据存储结构研究重点，以提高数据查询效率为目的，提出在内存数据库现有的N-Array存储结构中利用离散存储结构思想对其改进的方案，并给出具体的设计及实现方式。随后以属性选择查询为主要评估点，对N-Array存储结构和改进的存储结构的查询效率进行全方位分析和对比，最后得出结论：改进的存储结构在属性的选择查询上能更好的利用到系统的缓存优势，在内存数据库的查询效率上它是有意义的。
关键词： 内存数据库；存储结构；查询效率；缓存
中图分类号：TP391 文献标识码：A 文章编号：1671-7597（2012）1210064-02
随着当今的应用对数据库的要求越来越高，尤其表现在高实时性的要求上，传统的磁盘数据库已经开始显得很疲惫，很难再有更多的提高[1]。
在磁盘数据库系统中，数据是以文件格式存储在磁盘上，而在内存数据库中，数据以数据本身的形式直接存储在主存中；同时内存又有着读写速度比磁盘快、相比于磁盘顺序访问的随机访问，所有的的这些特点这些都使得内存数据库在实时性上有着比磁盘数据库先天的优势。目前在国内，中国联通的BSS（Business Sport Sysem，业务支撑系统），中国移动的Boss（Business & Operation Support System，业务运营支撑系统），中国电信的SIN（Shared Information Data，共享信息数据平台），以及HLR（Home Location Register，归属位置寄存器）、VLR（Visitor Loeation Register，拜访位置寄存器）等，都己开始采用了内存数据库技术[2]。内存数据库的研究及应用正朝者越来越深入与广泛的方向迈进[3]。
1 内存数据库查询优化的关键点
数据库的查询优化依赖于数据的存储方法、索引的结构等[4]。在查询优化的策略上，内存数据库和磁盘数据库关键点却是不同的：磁盘数据库查询优化的关键是减少磁盘的访问量（有时甚至用牺牲CPU时间代价的方式来减少磁盘I/O次数）。在内存数据库系统中，当前活动的事务需要访问的所有数据都在内存中，这样就完全没有了事务对磁盘的访问，数据的存在形式不再作为大量磁盘上存储的文件看待而作为内存中能直接寻址到的大量数据。由于通过指针访问数据，I/O不再是系统瓶颈，内存空间利用率和CPU的访问效率则成了内存数据库查询效率优化的关键[5]。
目前市场上虽然已经存在了一些商业化的内存数据库产品，但它们都不是很成熟。这些产品在存储结构的设计上，更多注重于内存空间的利用率，而忽略了CPU的内存访问效率及缓存的利用问题。这也导致现有内存数据库存储结构已成为当前内存数据库性能可逾越的一大瓶颈。所以业界对内存数据库的新的存储结构的研究与改进也一直在进行中。
2 改进存储结构的研究与设计
2.1 改进存储结构的提出
在N-Array存储结构中数据表中的记录是连续存放的，并且在记录内部，记录的属性也是按顺序存储。这种结构是非常节省存储空间的，而且实现起来也相对比较简单，目前主流的内存数据库包括SQLite、fastDB、eXtremDB都采用有这种存储结构对数据进行存储。
然而在内存数据库的实际应用中，N-Array存储结构查询效率却不够理想，尤其是在遇到属性选择查询时。因为在N-Array存储结构中，查询程序要访问某条记录的属性前必须要先要访问到整条记录，然后根据属性在记录内部具体的偏移位置拿到具体的属性值。因此在执行属性选择查询过程中，CPU会产生一些不必要的内存访问；再加上相同的属性值在内存中的不连续分布，查询时也很难充分利用到缓存。
在离散存储结构中，在对表的数据进行存储时先对表按照其属性进行分区，将一个完整的表划分为多个单独的子表，每个子表存储与原表中对应属性的数据。离散存储结构对表进行分区的思想就是以对提高属性查询效率为初衷的。因为把数据表中相同属性的值存放在一起，在根据某一属性查询时，查询程序就可以直接在相应的子表中进行，这能大大减少了对数据存储区域的访问。再加上相同属性值在内存中连续紧密分布特性，在属性选择查询时CPU也能更有效的利用到缓存。
但是离散存储结构也有它非常明显的局限性，当属性分区过多，查询性能会下降的特别厉害。由于在离散存储结构中同一条记录属性值的离散分布，它必须要处理数据重组问题。把属于同一记录的属性值组装到一起必须要做子表与子表的连接操作，理论上两个表做连接操作的代价与这两个表的各自记录数相乘的结果成正比，即笛卡尔积。在离散存储结构中，CPU的处理时间会因数据重组而大幅度增加，同时这种数据重组的中间结果也需要大量临时内存来保存直到查询结束，这往往使得离散存储结构有点得不偿失。
2.2 改进存储结构的设计与实现
改进的存储结构是在N-Array存储结构的上的改进，页面依然作为最基本数据储存单元，一个页面内存放一条或多条记录。不同N-Array存储结构之处在于：在页面内部，记录及其属性的存储策略发生了改变。
具体而言若要用改进的存储结构在内存页面中存储一个具有有n个属性的数据表时，在页面内就会有n+1个分区。第一个分区为页面头部信息，其余n个分区分别用来存放这n个不同属性的值。假设现有学生表（学号，姓名，年龄），若用改进的存储结构进行存储，页面内就有4个分区，学号属性一个分区，姓名属性一个分区，年龄属性一个分区。在每个分区内，属性按照其所属记录在页面内的顺序依次存储。此外还有一个非常重要的分区即页面头分区，虽然它不存放实际数据，但是它是改进的存储结构设计的核心。
页面头分区内的信息包括页面ID、各个属性分区在页面内的起始位置、页面内记录数、数据表的属性个数、各个属性的长度、页面剩余空间和一些其它的控制信息等。 由于属性还有定长和变长之分，记录如何确保在各个属性分区中准确地拿到自己的属性值，这必须得增加一些额外数据结构，这些数据结构也都在页面头分区中。
定长类型属性因其占用空间大小固定，每条记录的每个属性仅需要一个标志位就可以用来判断这个属性值是否为空即可。因此页面头部分区中，为每个定长类型属性设计一个位向量（页面内有多少条记录，该位向量就有多少位）。向量中的每一位对应一条记录，通过bit位是1还是0，来指示该记录定长属性值是否为空。
对于变长属性类型，在属性分区中就要记住各个属性的长度了，或者说每个属性值的起始位置。页面头部分区中，为每个定长类型属性设计一组指针，类似的，页面内有多少条记录，指针就有多少个，每个指针分别指向对应记录的属性值在属性分区中存储的末尾处。如果该指针数组内某个指针空时，则表示该指针所对应记录的变长属性值也为空。
假设有表Student（Number，Name，Age），并有三条记s1（001，Lucy，25）、s2（002，Lily，24）、s3（003，Joy，26）。其中Number为定长字符串，Name为变长字符串，Age为整型（也是定长）。改进存储结构示意图如下：
该图详细的阐明了页面头分区的设计，以及页面内各个属性分区的存储情况。表的第一个属性Number是定长属性，在页面头分区中会有一个标志单位向量（共三位），向量中每一位以0，1这个bit位来标识对应记录的属性值是否为空。第二个属性Name是变长属性，在页面头部分区中有一组结束位置指针，每个指针指向对应记录的Name属性值在Name属性分区中最后一位。第三个属性Age是定长的和Number类似。
3 查询性能效率分析
在改进的存储结构中，由于在页面内对数据表的属性的分区存储，使得相同属性在内存中的空间局部性更为紧密，在属性查询时会有更少的内存访问量，CPU也能有效利用到缓存。虽然改进的存储结构相比于N-Array储存结构，在属性查询过程中仍会产生一部分记录重组开销，但是由于页面头的特殊设计这部分开销也不再那么费时，而且这些数据重组发生在同一页面内，它的代价就不是那么高了。这也是改进存储结构和纯粹的离散存储结构的区别所在。
为了将将改进的存储结构与N-Array存储结构缓存利用率作对比：假设现有表Student（Number，Name，Age）。其中Number为定长字符串占用s1个字节，Name为变长字符串平均占用字节数为s2，Age为整型也是定长的占用s3个字节。数据库系统中缓存块的大小为s。由于无论N-Array存储结构还是改进的存储结构都是以页面作为最基本数据存储单元，设Student表占用N个页面，每个页面存放n条记录。再假设所有的记录Age属性值都大于20。
要执行的查询语句为：select Name from Student Where Age>20。该sql语句、查询的基本流程如下：查询处理器先找到Student表中所有的记录的Age属性值，然后根据Age的值的进行选择，最后获取符合一条件记录的Name属性值。
这是因为N-Array储结构会将与查询无关的Number属性值也放在缓存中，因此N-Array存储结构在执行完此类查询所有过程时中会产生更多的缓存失配次数。而在改进的存储结构中，根本不需要把Number属性放入缓存，这样节省了更多的多缓存空间放入其它有用的数据。
在改进的存储结构正是通过调整页面中记录的属性值的布局，加强了相同属性值在内存空间中的存放的局部性，故在根据属性值进行选择操作时能提高缓存利用率，减少缓存失配。在这一点上改进的存储结构明显要优于N-Array存储结构。
4 总结
在内存数据库和磁盘数据库的设计与实现上，理念已经有了巨大的变化。虽然业界已经有一些内存数据库，但是很多方面都有值得改进的地方，尤其在存储结构的设计上，而存储结构的设计对性能的影响又有起着决定性[6]。所以本文以目前内存数据库存储结构理论为基础，以提高数据库查询效率为出发点，深入的探讨了内存数据库优于查询的存储结构的设计与实现，并提出了改进的存储结构的设计与实现方案，它对内存数据库的查询效率上的提高是有意义的。
参考文献：
[1]杨武军、张继荣、屈军锁，内存数据库技术综述[J].西安邮电学院学报，2005，10（3）：95-99.
[2]曹猗宣、王晶，内存数据库在彩铃业务中的应用[J].计算机系统应用，2011（05）.
[3]李昭原，数据库技术新进展[M].2版，北京：清华大学出版社，2007.
[4]邹乐天，内存数据库索引技术研究[J].电脑与信息技术，2007，15（3）.
[5]杨艳、李炜、王纯，内存数据库在高速缓存方面的应用[J].现代电信科技，2011（12）.
[6]姜华，内存数据库的数据组织结构分析[J].电信快报，2010（12）.
作者简介：
刘哲益（1988-），男，湖南常德人，湖南大学信息与工程学院软件工程硕士生；边耐政（1969-），男，浙江嘉兴人，湖南大学信息与工程学院副教授。
关键词： 内存数据库；存储结构；查询效率；缓存
中图分类号：TP391 文献标识码：A 文章编号：1671-7597（2012）1210064-02
随着当今的应用对数据库的要求越来越高，尤其表现在高实时性的要求上，传统的磁盘数据库已经开始显得很疲惫，很难再有更多的提高[1]。
在磁盘数据库系统中，数据是以文件格式存储在磁盘上，而在内存数据库中，数据以数据本身的形式直接存储在主存中；同时内存又有着读写速度比磁盘快、相比于磁盘顺序访问的随机访问，所有的的这些特点这些都使得内存数据库在实时性上有着比磁盘数据库先天的优势。目前在国内，中国联通的BSS（Business Sport Sysem，业务支撑系统），中国移动的Boss（Business & Operation Support System，业务运营支撑系统），中国电信的SIN（Shared Information Data，共享信息数据平台），以及HLR（Home Location Register，归属位置寄存器）、VLR（Visitor Loeation Register，拜访位置寄存器）等，都己开始采用了内存数据库技术[2]。内存数据库的研究及应用正朝者越来越深入与广泛的方向迈进[3]。
1 内存数据库查询优化的关键点
数据库的查询优化依赖于数据的存储方法、索引的结构等[4]。在查询优化的策略上，内存数据库和磁盘数据库关键点却是不同的：磁盘数据库查询优化的关键是减少磁盘的访问量（有时甚至用牺牲CPU时间代价的方式来减少磁盘I/O次数）。在内存数据库系统中，当前活动的事务需要访问的所有数据都在内存中，这样就完全没有了事务对磁盘的访问，数据的存在形式不再作为大量磁盘上存储的文件看待而作为内存中能直接寻址到的大量数据。由于通过指针访问数据，I/O不再是系统瓶颈，内存空间利用率和CPU的访问效率则成了内存数据库查询效率优化的关键[5]。
目前市场上虽然已经存在了一些商业化的内存数据库产品，但它们都不是很成熟。这些产品在存储结构的设计上，更多注重于内存空间的利用率，而忽略了CPU的内存访问效率及缓存的利用问题。这也导致现有内存数据库存储结构已成为当前内存数据库性能可逾越的一大瓶颈。所以业界对内存数据库的新的存储结构的研究与改进也一直在进行中。
2 改进存储结构的研究与设计
2.1 改进存储结构的提出
在N-Array存储结构中数据表中的记录是连续存放的，并且在记录内部，记录的属性也是按顺序存储。这种结构是非常节省存储空间的，而且实现起来也相对比较简单，目前主流的内存数据库包括SQLite、fastDB、eXtremDB都采用有这种存储结构对数据进行存储。
然而在内存数据库的实际应用中，N-Array存储结构查询效率却不够理想，尤其是在遇到属性选择查询时。因为在N-Array存储结构中，查询程序要访问某条记录的属性前必须要先要访问到整条记录，然后根据属性在记录内部具体的偏移位置拿到具体的属性值。因此在执行属性选择查询过程中，CPU会产生一些不必要的内存访问；再加上相同的属性值在内存中的不连续分布，查询时也很难充分利用到缓存。
在离散存储结构中，在对表的数据进行存储时先对表按照其属性进行分区，将一个完整的表划分为多个单独的子表，每个子表存储与原表中对应属性的数据。离散存储结构对表进行分区的思想就是以对提高属性查询效率为初衷的。因为把数据表中相同属性的值存放在一起，在根据某一属性查询时，查询程序就可以直接在相应的子表中进行，这能大大减少了对数据存储区域的访问。再加上相同属性值在内存中连续紧密分布特性，在属性选择查询时CPU也能更有效的利用到缓存。
但是离散存储结构也有它非常明显的局限性，当属性分区过多，查询性能会下降的特别厉害。由于在离散存储结构中同一条记录属性值的离散分布，它必须要处理数据重组问题。把属于同一记录的属性值组装到一起必须要做子表与子表的连接操作，理论上两个表做连接操作的代价与这两个表的各自记录数相乘的结果成正比，即笛卡尔积。在离散存储结构中，CPU的处理时间会因数据重组而大幅度增加，同时这种数据重组的中间结果也需要大量临时内存来保存直到查询结束，这往往使得离散存储结构有点得不偿失。
2.2 改进存储结构的设计与实现
改进的存储结构是在N-Array存储结构的上的改进，页面依然作为最基本数据储存单元，一个页面内存放一条或多条记录。不同N-Array存储结构之处在于：在页面内部，记录及其属性的存储策略发生了改变。
具体而言若要用改进的存储结构在内存页面中存储一个具有有n个属性的数据表时，在页面内就会有n+1个分区。第一个分区为页面头部信息，其余n个分区分别用来存放这n个不同属性的值。假设现有学生表（学号，姓名，年龄），若用改进的存储结构进行存储，页面内就有4个分区，学号属性一个分区，姓名属性一个分区，年龄属性一个分区。在每个分区内，属性按照其所属记录在页面内的顺序依次存储。此外还有一个非常重要的分区即页面头分区，虽然它不存放实际数据，但是它是改进的存储结构设计的核心。
页面头分区内的信息包括页面ID、各个属性分区在页面内的起始位置、页面内记录数、数据表的属性个数、各个属性的长度、页面剩余空间和一些其它的控制信息等。 由于属性还有定长和变长之分，记录如何确保在各个属性分区中准确地拿到自己的属性值，这必须得增加一些额外数据结构，这些数据结构也都在页面头分区中。
定长类型属性因其占用空间大小固定，每条记录的每个属性仅需要一个标志位就可以用来判断这个属性值是否为空即可。因此页面头部分区中，为每个定长类型属性设计一个位向量（页面内有多少条记录，该位向量就有多少位）。向量中的每一位对应一条记录，通过bit位是1还是0，来指示该记录定长属性值是否为空。
对于变长属性类型，在属性分区中就要记住各个属性的长度了，或者说每个属性值的起始位置。页面头部分区中，为每个定长类型属性设计一组指针，类似的，页面内有多少条记录，指针就有多少个，每个指针分别指向对应记录的属性值在属性分区中存储的末尾处。如果该指针数组内某个指针空时，则表示该指针所对应记录的变长属性值也为空。
假设有表Student（Number，Name，Age），并有三条记s1（001，Lucy，25）、s2（002，Lily，24）、s3（003，Joy，26）。其中Number为定长字符串，Name为变长字符串，Age为整型（也是定长）。改进存储结构示意图如下：
该图详细的阐明了页面头分区的设计，以及页面内各个属性分区的存储情况。表的第一个属性Number是定长属性，在页面头分区中会有一个标志单位向量（共三位），向量中每一位以0，1这个bit位来标识对应记录的属性值是否为空。第二个属性Name是变长属性，在页面头部分区中有一组结束位置指针，每个指针指向对应记录的Name属性值在Name属性分区中最后一位。第三个属性Age是定长的和Number类似。
3 查询性能效率分析
在改进的存储结构中，由于在页面内对数据表的属性的分区存储，使得相同属性在内存中的空间局部性更为紧密，在属性查询时会有更少的内存访问量，CPU也能有效利用到缓存。虽然改进的存储结构相比于N-Array储存结构，在属性查询过程中仍会产生一部分记录重组开销，但是由于页面头的特殊设计这部分开销也不再那么费时，而且这些数据重组发生在同一页面内，它的代价就不是那么高了。这也是改进存储结构和纯粹的离散存储结构的区别所在。
为了将将改进的存储结构与N-Array存储结构缓存利用率作对比：假设现有表Student（Number，Name，Age）。其中Number为定长字符串占用s1个字节，Name为变长字符串平均占用字节数为s2，Age为整型也是定长的占用s3个字节。数据库系统中缓存块的大小为s。由于无论N-Array存储结构还是改进的存储结构都是以页面作为最基本数据存储单元，设Student表占用N个页面，每个页面存放n条记录。再假设所有的记录Age属性值都大于20。
要执行的查询语句为：select Name from Student Where Age>20。该sql语句、查询的基本流程如下：查询处理器先找到Student表中所有的记录的Age属性值，然后根据Age的值的进行选择，最后获取符合一条件记录的Name属性值。
这是因为N-Array储结构会将与查询无关的Number属性值也放在缓存中，因此N-Array存储结构在执行完此类查询所有过程时中会产生更多的缓存失配次数。而在改进的存储结构中，根本不需要把Number属性放入缓存，这样节省了更多的多缓存空间放入其它有用的数据。
在改进的存储结构正是通过调整页面中记录的属性值的布局，加强了相同属性值在内存空间中的存放的局部性，故在根据属性值进行选择操作时能提高缓存利用率，减少缓存失配。在这一点上改进的存储结构明显要优于N-Array存储结构。
4 总结
在内存数据库和磁盘数据库的设计与实现上，理念已经有了巨大的变化。虽然业界已经有一些内存数据库，但是很多方面都有值得改进的地方，尤其在存储结构的设计上，而存储结构的设计对性能的影响又有起着决定性[6]。所以本文以目前内存数据库存储结构理论为基础，以提高数据库查询效率为出发点，深入的探讨了内存数据库优于查询的存储结构的设计与实现，并提出了改进的存储结构的设计与实现方案，它对内存数据库的查询效率上的提高是有意义的。
参考文献：
[1]杨武军、张继荣、屈军锁，内存数据库技术综述[J].西安邮电学院学报，2005，10（3）：95-99.
[2]曹猗宣、王晶，内存数据库在彩铃业务中的应用[J].计算机系统应用，2011（05）.
[3]李昭原，数据库技术新进展[M].2版，北京：清华大学出版社，2007.
[4]邹乐天，内存数据库索引技术研究[J].电脑与信息技术，2007，15（3）.
[5]杨艳、李炜、王纯，内存数据库在高速缓存方面的应用[J].现代电信科技，2011（12）.
[6]姜华，内存数据库的数据组织结构分析[J].电信快报，2010（12）.
作者简介：
刘哲益（1988-），男，湖南常德人，湖南大学信息与工程学院软件工程硕士生；边耐政（1969-），男，浙江嘉兴人，湖南大学信息与工程学院副教授。