基于Hadoop的分布式SQL数据库索引设计与实践∗

陈 红

（昌吉职业技术学院 昌吉 831100）

1 引言

随着数据规模的增长，传统的SQL数据库管理模式已经无法有效地管理海量的数据库数据［1］。随着云计算等技术在信息系统等技术领域的应用，分布式系统为处理海量数据提供了一个全新的方案［2］，如何将分布式系统应用到数据管理当中已经成为了一个研究的热点。SQL数据库索引是海量数据管理与检索的关键问题。树形索引［3］是当前流行的SQL数据库索引结构，其中以R树家族［4］最为突出。随着分布式系统研究的深入，分布式索引逐渐成为SQL数据库索引的研究热点［5］，文献［6～7］研究了MR-tree、R树和多级R-tree的并行化实现，文献［8］对四叉树进行面向列式存储扩展改进，文献［9］将VoR-Tree、双层倒排网格索引、SQL数据库的k近邻查询与MapReduce编程模型相结合进行分布式改造。

针对海量数据的索引需求，本文将SQL数据库索引与云计算技术相结合，提出了基于Hadoop平台的分布式SQL数据库索引，并从架构设计、数据划分和局部索引和全局索引构建等方面出发，在Hadoop下设计并实现了分布式SQL数据库索引。同时。最后本文搭建了Hadoop环境并进行实验证明了改进后的算法可以有效减少数据检索时间，提高整体性能，高并发、低成本、高可靠的完成数据检索任务。

2 索引结构设计

本文设计的基于HDFS的分布式SQL数据库索引采用分层的分布式索引结构，分层式分布式索引结构首先将数据库数据按照SQL数据库分布进行划分，将SQL数据库上临近的数据划分到一个分区当中，再对每一个分区当中的数据构建一个局部索引，并将局部索引以及该分区数据存储到数据节点当中。当所有数据划分完毕并且所有局部索引构建完成以后，在主节点中依据各个局部索引的根节点构建一个全局索引，存在主节点当中。由于主节点中的全局索引只保存了局部索引的根节点的信息，全局索引的大小得到了限制，减轻了主节点存储与计算的负担［10］，同时，由于全局索引的大小较小，在程序运行时可以将全局索引一次性加载到内存中，对全局索引进行检索时避免了磁盘的IO，提升了数据检索效率［11］。分层式SQL数据库索引结构如图1所示。

图1 分层式分布式索引

本文索引由全局索引、局部索引、数据分片三层构成，索引构建主要分为如下三个步骤：

全局索引：全局索引是指针对整个数据集建立一个统一的索引，每一个索引指向一个节点或一个数据块，实现算法相对比较简单。全局索引可以看做是局部索引的缓存，基于全局索引的查询操作，只需要访问相关的节点或数据块即可，能够减少数据读取时间，提高检索效率。

局部索引：局部索引是指针对每一个数据分区所建立的独立索引，数据块之间的检索也相互独立，具有良好的容错能力；同时也有利于数据块的局部更新和索引重建。

数据分片：文件上传到HDFS上会被分成若干文件块并存储到Datanode上。每个文件块的大小应小于HDFS文件块的大小，如果文件块的大小大于HDFS文件块大小，那么单个数据分片就可能会被存到多个不同的Datanode当中，这样导致在进行检索时需要通过网络从不同的Datanode上获取数据，这样会降低数据检索的效率。因此，应控制数据分片与其对应的索引大小和小于HDFS的文件块大小。

数据集划分成若干个数据分片：

局部索引构建：根据每一个数据分片的数据，构建局部索引，并将构建的索引存储到对应的Datanode中。

全局索引构建：根据数据划分以及局部索引构建的结果，在Namenode上构建一个全局索引。

3 SQL数据库划分

其中，S为待划分数据库数据大小，一般是128M，α表示膨胀系数，膨胀系数主要的考虑因素为数据库数据与其局部索引的大小差距，一般采用0.2～

本文基于海量SQL数据库数量，直接建立索引将会使索引太庞大，严重影响数据检索效率［12］，需要将整个数据库数据按照一定规则进行划分后建立局部索引，这样可以避免上述状况，选取一个合适的SQL数据库划分方案十分重要。

3.1 SQL数据库划分规则

SQL数据库划分是构造分布式索引的关键环节，划分规则的好坏直接决定了索引的检索效率，在进行数据划分时，应尽量遵循如下两个原则：

1）生成若干个大小基本相等的分区，且分区大小不超过HDFS数据块大小。如果划分分区超过HDFS数据块大小可能导致该分区数据存储到不同的HDFS上，影响查询效率。如果分区大小差距过大，部分分区数据量太少，会导致索引节点数增加，索引层数高度增加，同时会导致热区问题，影响查询效率。

2）生成的数据分区要保证SQL数据库局部性。在进行范围查询时，应当尽量减少IO操作，减少读写磁盘的次数。如当e1和e2SQL数据库上距离较近，则e1和e2应当分配到同一个分区当中。划分结果以及其局部索引需要存储到同一个HDFS块中，所以划分的数据分区以及该分区的局部索引大小之和应小于HDFS块大小。确定划分区域数量为0.3即可［13］。

本文采用STR树叶节点生成算法［14］对数据进行划分，图2为STR树叶节点划分方式，假设有N个数据，首先将数据按照x坐标值的大小进行排序，平均生成[n]个分组，其中n为分区数量，这样生成的分组中每个分组至少包含[N/n]个数据。然后在得到的分组结果中以y的坐标值大小进行排序，每[N/n]个数据被划为一组，生成n个分组。如果数据结构为多边形，则按照其最小外包矩形中心点进行排序。根据以上算法可以得知，如果数据均匀分布在SQL数据库区域上，那么这种划分方式与网格分割［15］效果类似，但是如果数据分布极不均匀，那么这种划分方式能够更好地对数据进行划分。

图2 STR叶子节点分割示意图

STR叶节点划分方式依据数据的SQL数据库临近，对数据进行了聚类处理［16］，能够有效地应对数据分布不均匀的情况，但是在划分过程中，需要进行多次排序操作，处理海量数据的效率不高，因此，考虑首先对数据进行采样处理，然后采用Ma⁃pReduce进行并行划分，具体实现过程将在下一节详细描述。

3.2 并行数据划分

本文首先对SQL数据库中的数据进行充足随机采样，因为足够的采样数据可以代表整体数据的分布趋势及分布规律，通过MapReduce对任意采样的数据块实施数据排序，采样的数据块进行X排序后，将X分组中x坐标的最大值与下个相邻分组的X最小值的平均值作为两个分组直接的界线值，全部分组中的第一个分组与最后一个分组的界线值分别选择起始X值与结束X值；同理可得到y坐标的界线值。最终得到一个划分函数func确定一个分区

4 基于改进R树的分布式索引构建及存储

通过数据划分得到了划分后的数据分区，将根据每一个数据分片的结果单独构建R树索引，保证所有的数据都在索引范围内，采用一种改进的R树生成方式构建局部索引，提升在分区中查询数据的效率。

4.1 局部索引构建与存储

假设经过数据划分的数据块中有k个数据，相应则在数据划分过程中建立了k个MBR，在本节使用一种改进的R树生成算法Reduce过程中构建数据的局部R树索引。在map的阶段已经获取了数据分片中所有数据的MBR，采用动态插入MBR的方式构建R树。在插入数据过程中，如果向一个饱和节点中插入数据，首先检查溢出节点表中是否包含此节点，如果已经包含且该节点的溢出节点没有饱和则直接插入数据即可，如果溢出节点表中尚未包含该节点，则在溢出节点表中为该节点创建一个溢出节点，并向溢出节点中插入数据。若一个节点的溢出节点也饱和，则对该节点及其溢出节点进行归并分裂操作，写回到R树种。当所有对象都访问完，如果溢出节点表中还有数据，则进行一次强制写回操作，最后将生成的R树索引及分区数据序列化到HDFS上。

图3 局部索引存储格式

在进行数据划分时，已经在每个数据分区中为局部索引预留了SQL数据库，所以可以直接将局部索引和数据存储在同一个HDFS块中。数据及其局部索引的存储格式如图3所示，分为索引元数据部分、局部索引部分和数据部分。其中，第一部分为树结构区存储R树的结构信息，包括索引的大小即树结点数据区域的大小、树的高度、树中每个结点的容量以及SQL数据库对象的个数。根据树的高度以及结点容量可以计算出结点对象的个数。中间区域为树结点数据区域，该区域存放的是树结点信息，每个结点对象存放其子节点的信息（子节点的位置指针及子节点的MBR），最后一个区域为数据区域记录每一个属于该区域的数据。在信息查询时一般不会加载数据，而是只把R树的结构信息加载到内存中，当只需要进一步查询时才加载具体的数据。

4.2 全局索引构建与存储

本文的设计思想是用户在每一次对数据的操作都会先经过全局索引的检索，然后根据全局索引的检索情况在对局部索引进行检索。本节将介绍全局索引的构建和存储。由于全局索引使用的频率高且数据量很小，因此，全局索引构建完成后可以将其常驻于Namenode节点的内存中。

全局索引的存储结构与局部索引类似，具有树结构信息以及树结点信息两个部分组成，不同之处为在全局索引的树叶子结点数据中存放的不是具体的数据的指针与外包矩形，而是存放的相应的HDFS文件路径以及局部索引根结点的MBR信息。从而实现全局索引与局部索引的关联。全局索引的构建在所有局部索引构建完成之后进行。由于分区数量不会过多。因此全局索引的大小不会过大，不需要分布式执行。全局索引采用常规的R树生成方式即可。

5 实验分析

5.1 实验环境

本实验借助虚拟机搭建了具有6个节点的Ha⁃doop集群，每个节点分配4G内存和一定SQL数据库的硬盘，节点上运行Ununtu14.0操作系统以及Hadoop2.6.4，并支持Linux下Java8的操作环境Ha⁃doop集群中包括1个Master和5个Slave，Master主要负责数据的整体调度，Slave作为具体的执行者负责存储数据和处理数据。

5.2 区域查询实验

由于本文索引采用多级分布式索引结构，因此在进行区域查询时与普通单机SQL数据库索引查询操作不同。在区域查询操作中首先通过全局索引将SQL数据库查询操作划分到不同的数据节点中进行查询，最终将数据节点中查询到的数据聚合为最终的数据。

实验使用谷歌地图数据集［17］，大小约为9.3G，查询范围由0.0001%～1%变化，分别选取工作节点数目为2、4、6和单机状态，测试节点个数的变化对查询时间的影响。实验数据如图4所示。

图4 区域查询实验结果

由图4可得出，当查询区域特别小时，单机状态下查询所需时间并没有明显劣势，但是随着查询区域的扩大，查询操作耗时呈指数型增长，这是因为单台计算机本身性能有限。通过对比2、4、6个工作节点的查询耗时，可看出相同数据量、相同查询区域的情况下，数据查询时间随着工作节点的增多而减少，这是因为具体的查询操作被分配到了数据节点中执行，提高了检索性能。由此得出，本文设计的分布式SQL数据库索引提高了检索性能，适用于处理海量数据。

5.3 k近邻查询实验

k近邻查询的基本思想是，给定一个参考点的坐标，查询离该点最近的k个数据。基于本文索引的k临近查询操作共分为3个步骤分别为全局knn操作，局部knn操作，局部knn结果检查合并。其中全局knn操作由于计算量较小在Master节点执行即可。局部knn操作和检查在Map阶执行。结果合并阶段在Reduce中执行。

实验同样使用谷歌地图数据集，大小约为9.3G，n的范围从1～10000变化，实验随机选取若干点进行多次实验，取最终的平均值，实验分别选取工作节点数目为2、4、6和单机状态，测试节点个数的变化对查询时间的影响。实验数据如图5所示。

如图5所示在k近邻查询实验中随着k值的增加，查询耗时也在增加。这是因为k值越大，需要检索的范围越大，查询操作耗费的时间也就越多，并且耗时增幅越明显。这是由于在k值比较小时，集群并未发挥全部性能。因此小幅度增大k值，查询所需时间增长幅度较小。然而当k值增大到一定程度，集群已经发挥全部性能，此时继续增长k值，查询操作耗时就会出现线性增长的状况。当k值较大时k近邻查询所需时间随着工作节点数量的增加而减小，而当k值较小时，查询操作的耗时几乎不受节点数量的影响。这证实了n值较小时，k近邻查询只在比较少的节点中进行。而当k值较大时，k近邻查询将在集群所有节点中并行执行。

图5 k近邻查询实验结果

6 结语

由于传统的单机SQL数据库索引技术面对大规模数据时计算能力不足，索引效率低，因此本文还将SQL数据库索引技术与云计算技术相结合，提出了基于Hadoop平台的分布式SQL数据库索引。本文从索引结构设计、数据划分、局部和全局索引构建和存储等方面，详细阐述了分布式SQL数据库索引的实现，最后搭建Hadoop平台进行了测试。在今后的研究工作中，重点会放在对R树算法更好的优化过程中。同时，本文主要是针对二维数据上的研究，日后的研究将不仅仅局限在二维数据上，将研究的目光扩展到更高维上。

［1］贺瑶，王文庆，薛飞.基于云计算的海量数据挖掘研究［J］. 计算机技术与发展，2013，23（02）：69-72.

［2］曲家朋，廖海.海量文件存储技术研究［J］.机电工程技术，2016（08）：359-362.

［3］史晓楠，徐澜，徐丹丹，等.一种改进的基于Hash算法及概率的k-mer索引方法［J］.通信电源技术，2017，34（03）：70-72，74.

［4］邵华，江南，胡斌，等.利用GPU的R树细粒度并行STR方法批量构建［J］.武汉大学学报（信息科学版），2014，39（09）：1068-1073.

［5］翁海星，宫学庆，朱燕超，等.集群环境下分布式索引的实现［J］. 计算机应用，2016，36（01）：1-7+12.

［6］刘义，景宁，陈荦，等.MapReduce框架下基于R-树的k-近邻连接算 法［J］. 软 件学报，2013，24（08）：1836-1851.

［7］刘义，陈荦，景宁，等.基于R-树索引的Map-Reduce空间连接聚集操作［J］.国防科技大学学报，2013，35（01）：136-141.

［8］杨建思.一种四叉树与KD树结合的海量机载LiDAR数据组织管理方法［J］.武汉大学学报（信息科学版），2014，39（08）：918-922.

［9］杨文奇，刘杰，陈飞轮.基于MapReduce的并行VoR-Tree索引［J］. 地理空间信息，2013，11（06）：109-111.

［10］陈润健，王金凤.并行计算和稀疏存储在模糊积分上的应用［J］. 计算机应用研究，2017（01）：1-9.

［11］赵辉，杨树强，陈志坤，等.基于MapReduce模型的范围查询分析优化技术研究［J］.计算机研究与发展，2014，51（03）：606-617.

［12］杜朝晖，朱文耀.云存储中利用属性基加密技术的安全数据检索方案［J］.计算机应用研究，2016，33（03）：860-865.

［13］王蛟龙，周洁，高慧，等.基于局部环境形状特征识别的移动机器人避障方法［J］.信息与控制，2015，44（01）：91-98.

［14］昌春艳，王沁，田锟，等.优化STR模型的实证研究［J］.武汉理工大学学报（信息与管理工程版），2013，35（04）：565-569.

［15］施逸飞，熊岳山，谢智歌，等.基于多核学习的快速网格分割算法［J］.计算机辅助设计与图形学学报，2015，27（11）：2031-2038.

［16］黄良韬，赵志诚，赵亚群.基于随机森林的密码体制分层识别方案［J］. 计算机学报，2017（07）：1-19.

［17］李艳霞，刘学，党寿江，等.网管系统中基于谷歌地图的拓扑可视化实现［J］.计算机工程与设计，2013，34（02）：681-685.