数据库索引技术概述

母凤雯

摘要：随着数据库技术的发展，数据库索引技术面临着巨大的挑战，为了了解数据库索引技术的发展方向，文章对数据库索引技术的发展现状进行了简要概述。文章从数据库技术的发展出发，阐述了数据库索引技术发展的必然方向，简单说明了传统的数据库索引技术，例如ISAM索引、b+树、Hash索引，并对可能成第三阶段数据库主流的面向对象数据库的索引技术，例如结构索引、路径索引、多重索引进行了阐述。文章重点对当前大数据时代下，基于大数据的数据库索引技术进行梳理和总结，指出大数据环境中为应对数据容量大、速度快、种类多、价值密度低的4v特点而发展出的索引机制的特点。文章最后对数据库索引的发展方向进行思考讨论，进一步说明数据库索引技术下一步的发展可能方向。

关键词：数据库索引；ISAM索引；b+树；Hash索引；结构索引；路径索引；多重索引；大数据

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）25-0009-03

Abstract： With the development of database technology， database indexing technology is facing great challenges. In order to understand the development direction of database indexing technology， this paper gives a brief overview of the development of database indexing technology. Based on the development of database technology， this paper expounds the inevitable direction of the development of database indexing technology， and briefly describes the traditional database indexing technology， such as ISAM index， b + tree， Hash index， and elaborates the indexing techniques of object-oriented database which may be the mainstream of the third stage database， such as structural indexing， path indexing， multiple indexes. This paper focuses on the database indexing technology Based on large data in the current large data age， and points out that the index mechanism developed in the large data environment to cope with the 4v characteristics of data capacity， speed， variety and low value density specialty. Finally， the article discusses the development direction of the database index， and further explains the possible direction of the development of the database indexing technology.

Key words： Database index； ISAM index； b + tree；Hash index； structure index； path index； multiple index； large data

數据库索引是数据库查询优化的重要方法，它的一个主要目的就是加快检索表中数据，亦即能协助信息搜索者尽快地找到符合限制条件的记录ID的辅助数据结构[1]。数据库自1962年发展至今，历时50多年，共三个阶段。第一个阶段为数据独立性低，编程复杂度高，用户使用难度大的层次和网状数据库。第二个阶段也是当前仍然作为主流数据库技术的关系数据库，它以1970年E.F.Codd博士提出的关系模型为数学基础[2]，数据独立性高，用户使用通用的SQL语言操作简单。从20世纪80年代以来，关系数据库系统逐渐代替网状数据库系统和层次数据库系统而占领了市场[3]。近年，随着互联网技术的发展以及应用领域对数据库技术的需求，层次和网状数据库和关系数据库这类传统的数据库技术已经难以满足当今的现实需求。为了适应数据的复杂性，处理的复杂性，数据结构的动态性，数据的时间性等[4]，产生了新一代数据库技术，例如：用于存储二维，三维或更高维空间的空间坐标以及空间范围相关的空间数据的空间数据库技术[5]；用于海量交易数据，海量交互数据，海量处理数据的非关系型数据库[6]；数据库技术与面向对象技术结合的面向对象数据库技术[7]；应对多媒体信息存取需求日益增多的多媒体数据库[8]等。这些新型数据库在数据模型，数据存储方面与传统型数据库有着本质的差别，因此，传统数据库所用到的索引技术已经不再适合新型数据库。

1 传统数据库索引技术

传统数据库索引技术根据数据存放的物理结构不同可分为聚集索引和非聚集索引[9]，聚簇索引是按照数据存放的物理位置为顺序的，而非聚簇索引就不一样了；聚簇索引能提高多行检索的速度，而非聚簇索引对于单行的检索很快[10]。在传统数据库索引技术中常用的索引数据结构主要有ISAM索引，HASH索引，和B+树索引[11]。endprint

1.1 ISAM索引

ISAM索引是基于树组织的索引数据结构，既支持等值查找也支持范围查找的静态结构[12]。ISAM树是一颗二叉树，其中数据全部存储在树的叶子页面，非叶子节点只存储索引指针，溢出页面链接到叶子页面。

1.2 b+树

B+树的树结构是多路搜索的平衡树，数据仅存储在叶子节点中，非叶子结点引导搜索，同时为了有效检索所有的叶子页面，叶子节点间通过指针相互链接[12]。B+树的检索方式与ISAM索引一样，但是在进行插入删除操作的时候树结构动态变化以保持树结构的平衡，故不存在添加溢出页面。

1.3 Hash索引

哈希索引的核心思想是利用哈希函数，将搜索数据的值映射到一个数字，然后找到搜索数据目录所在的页。因此，哈希索引只支持等值检索不能支持范围检索。

2 面向对象数据库索引技术

在关系数据库系统中，索引建立在單个类（或关系）的属性上，以加快搜索。在面向对象的数据库中，针对类的查询的访问范围不仅包括类，而且还包括类的所有子类，类由集聚关系和继承关系实现[14]。因此，面向对象数据库的索引技术主要涉及支持对象的嵌套属性和继承层次结构的查询[15]。在面向对象的DBMS框架中定义的索引技术可以分为结构索引和路径索引[13]，多重索引。

2.1 结构索引

目前大多数面向对象的查询语言允许针对对象属性查询谓词，因此结构索引基于对象属性。结构索引技术可以分为支持嵌套谓词的嵌套索引技术，以及支持针对继承层次结构查询的类层次索引技术。嵌套属性索引查找谓词可以指定在该类的任意嵌套属性上，一个查询返回一个目标类的实例对象集合[16]，其检索性能很好，但是维护的代价相当高。类层次索引技术则是一种更新成本不高的索引技术，类的属性 [Aa]的类层次索引，是以该类为根的类层次上所有类的属性的一个单一索引。索引属性是建立在其上的属性，而索引类是索引建立在这些类属性上的类层次的根[17]。

2.2 路径索引

在嵌套索引中，如果给定一个关键词，叶结点只记录了关联此关键词路径中起始对象的对象标识。我们研究路径索引（PathIndex，简称为PX），以记录所有以该关键词结束的路径[17]。

2.3 多重索引

如果将一条路径分裂成若干条子路径，并在每一条路径上建立嵌套索引，可以在一定程度上降低修改索引所带来的开销[17]。

3 基于大数据的数据库索引技术

随着大数据时代的到来，传统的数据处理技术，如数据库和数据仓库，已不足以处理数据容量越来越大；数据量增长越来越快，需要处理的速度和响应越来越快；数据种类多样的大数据[16]。大数据存储方式的根本改变，要求大数据的索引机制必须满足支持多种査询、支持高效检索和易于维护等要求。为了解决大数据査询处理问题，需要针对大数据环境建立新的索引结构[27]。下表根据其索引结构不同将索引技术分为二级索引，双层索引，多维索引，基于Hadoop的索引技术。

3.1 二级索引

二级索引是指大多数基于key-value模型来存放数据的管理系统采用的索引技术。该类数据库通过key进行数据的查询，修改和删除等操作，比如HBASE，dyname等数据库均是以key为索引。现有Key-vlaue型数据库在存储数据时通常采用b+树索引，该结构对rowkey查询具有较高效率，但是对于非rowkey查询效率低下且无法提供复杂查询。许多学者对此提出了改进的索引策略，Parag Agrawal等人提出了Asynchronous View[18]，文章提出了远程视图表（remote view tables）和本地视图表（local view tables）用来实现非rowkey的异步索引方式，其思想是为某个查询建立一个与原始表一样的远程视图表，并为每个节点的数据建立一个本地视图表，在查询时使用远程视图表以提高查询效率，节点数据更改时仅更新本地视图表以降低索引维护代价。Zou等人提出了complemental clustering index，简称 CCIndex[20]，该方案中索引表存放了完整的行数据，查询时通过顺序扫描查找数据而非当前使用的随机读取方式，提高了查询效率；为每个文件进行备份，提高可靠性；为保证数据的容错性引入聚类检查表，保证数据快速恢复。针对key-value存储不支持LBS（location based services）所必需的丰富查询功能所需的多属性访问，Nishimura S提出了MD-HBase[21]。

3.2 双层索引

双层索引方案主要是为了满足数据的海量性以及系统的可扩展性而提出来的，其索引部分包括局部索引和全局索引[22]。目前许多学者对该方向进行了研究，Wu S等人提出了Efficient B-tree[23]，该索引由本地b+树索引和BATON网构成，它首先将数据分片后随机分配到各个节点，将索引服务器组织为一个结构化的对等网络BATON[24]，使得服务器之间可以路由查询，实现全局索引，然后为每个节点建立b+树索引实现局部索引。Efficient B-tree[23] 中相同的值可能位于同一个节点或不同节点中，如果B + -tree对这些值进行索引，会因数据太大导致查询缓慢。为降低开销，Huang B等人提出了TLB-index[25]，其基本思想与Efficient B-tree[23]一致，索引也是由b+树索引和BATON网构成，不同点是TLB-index[25]为每个不同的值构建一个位图。然后为所有位图构建一个B +树。

3.3 多维索引

多维索引主要应用处理图像信息，地理信息数据的空间数据库[26]。Zhang X等人提出了EMINC[27]，该方法为每个局部节点建立RD-tree索引，并为部分局部节点建立R-tree全局索引，可以为大数据管理系统提供快速查询处理和有效的索引维护。为了增加大数据管理系统的可扩展性，支持大规模的查询，Jinbao Wang等人提出了RT-CAN[28]，该索引由CAN路由协议作为全局索引，R-tree作为局部索引，其实现是通过适用于多维搜索的CAN维护基于局部索引的全局索引，全局索引被分配到每个节点，每个节点只维护全局索引的一部分，然后为每个节点的数据建立R-tree索引，并将R-tree映射到CAN节点。该方法具有可扩展性和容错能力，并支持等值，范围查询和KNN查询。为使多维索引能在极端动态的环境下运行，George Tsatsanifos等人提出了MIDAS[29]，它将虚拟节点作为基本实体，以避免物理节点离开，故障等造成的不良影响，一个物理节点对应多个虚拟节点，一个虚拟节点对应分层索引KD-tree的一个叶子，并且每个节点关联一个从根路径开始的二进制标识符。endprint

3.4 基于Hadoop的索引技术

Hadoop已经成为大数据存储和处理的标准平台，Hadoop的HDFS提供大数据存储，MapReduce并行编程模型实现大数据并行査询和处理[30]，为提高其查询效率，Abouzeid等人提出了Hadoop DB[31]，基本思想是使用Hadoop作为任务协调器和网络通信层来连接多个单节点数据库系统，然后使用MapReduce框架在各节点间进行查询并行化，实现了大规模数据的并行处理。为解决Hadoop的性能通常与配置良好的并行数据库管理系统不兼容问题，J Dittrich等人提出了Hadoop++[32]，Hadoop++在不改变Hadoop底层框架的情况下，通过自定义函数对Hadoop进行非入侵式优化。为使Hadoop处理速度更快，Dittrich J等人提出了HAIL[33]（Hadoop Aggressive Indexing Library），HAIL[33]是入侵式方法，它更改HDFS的上传管道，然后在每个数据块副本上创建不同的聚簇索引，这样HAIL数据上传和查询均优于 Hadoop。

4 结束语

随着大数据时代的来临，以及各个学科邻域信息系统的逐步成熟，传统数据库索引技术明显已无法满足时代的需求，基于大数据的数据库索引技术和面向对象数据库索引技术拥有巨大的潜力。虽然目前有许多学者对索引技术领域做出了不少相关研究，但是成果并不成熟且没有得到广泛的应用。本文对数据索引技术的发展变化做出了简单的梳理，希望能为数据库索引技术的研究者提供借鉴。

参考文献：

[1] 欧萍. 数据库索引技术应用[J]. 电子科技，2011（9）：146-148.

[2] Codd E F. A relational model of data for large shared data banks （Reprinted from Communications of the ACM， June， pg 377-87， 1970）[J]. M.d.computing Computers in Medical Practice， 1998， 15（3）：162-166.

[3] 閻同喜. 数据库技术发展概述[J]. 机械管理开发，2004（5）：80-82.

[4] 诸峰，张再跃. 数据库技术在现代应用中的发展[J]. 世界科技研究与发展，2002（2）：65-68.

[5] 郭菁，周洞汝，郭薇，胡志勇. 空间数据库索引技术的研究[J]. 计算机应用研究，2003，（12）：12-14.

[6] 申德荣，于戈，王习特，聂铁铮，寇月. 支持大数据管理的NoSQL系统研究综述[J]. 软件学报，2013（8）：1786-1803.

[7] 汪琛，胡浩民. 面向对象数据库技术的发展与前景[J]. 福建电脑，2005（5）：17-18.

[8] 王娣. 多媒体数据库技术综述[J]. 情报杂志，2001（11）：5-6+9.

[9] 邓体俊. 数据库索引技术的应用[J]. 电脑知识与技术，2010（36）：10212-10214.

[10] 数据库索引的实现原理.http：//blog.csdn.net/kennyrose/article/details/7532032/

[11] 胡九龙，赵捧未. 数据检索中索引技术研究[J]. 科技情报开发与经济，2004（1）：210-211.

[12] Grillmeyer O. Database Management Systems[M]. 清华大学出版社， 2000.

[13] Bertino E， Guglielmina C. Path-index： An approach to the efficient execution of object-oriented queries[J]. Data & Knowledge Engineering， 1993， 10（1）：1-27.

[14] Bertino E， Catania B， Chiesa L. Definition and analysis of index organizations for object-oriented database systems ☆[J]. Information Systems， 1998， 23（2）：65-108.

[15] Bertino E， Foscoli P. Index Organizations for Object-Oriented Database Systems[J]. IEEE Transactions on Knowledge & Data Engineering， 1995， 7（2）：193-209.

[16] 陈仲民，王雪. 面向对象数据库的索引技术[J]. 计算机工程与科学，2000（6）：100-104.

[17] 冯黎，赵治斌. 初探面向对象数据库及其索引技术[J]. 中国科技信息，2009（13）：96-97.

[18] Chen J， Chen Y， Xiaoyong D U， et al. Big data challenge： a data management perspective[J]. Frontiers of Computer Science， 2013， 7（2）：157-164.

[19] Agrawal P， Silberstein A， Cooper B F， et al. Asynchronous view maintenance for VLSD databases[C]// ACM SIGMOD International Conference on Management of Data. ACM， 2009：179-192.endprint

[20] Zou Y， Liu J， Wang S， et al. CCIndex： A Complemental Clustering Index on Distributed Ordered Tables for Multi-dimensional Range Queries[M]// Network and Parallel Computing. Springer Berlin Heidelberg， 2010：247-261.

[21] Nishimura S， Das S， Agrawal D， et al. MD-HBase： A Scalable Multi-dimensional Data Infrastructure for Location Aware Services[C]// IEEE International Conference on Mobile Data Management. IEEE， 2011：7-16.

[22] 馬友忠，孟小峰. 云数据管理索引技术研究[J]. 软件学报，2015（1）：145-166.

[23] Wu S， Jiang D， Ooi B C， et al. Efficient B-tree based indexing for cloud data processing[J]. Proceedings of the Vldb Endowment， 2010， 3（1-2）：1207-1218.

[24] H. V. Jagadish， B. C. Ooi， and Q. H. Vu. Baton： A balanced tree structure for peer-to-peer networks. In VLDB， 2005.

[25] Huang B， Peng Y X. An efficient two-level bitmap index for cloud data management[C]// IEEE， International Conference on Communication Software and Networks. IEEE， 2011：509-513.

[26] 谭宁. 基于R-树多维索引结构的优化研究与应用[D].湘潭大学，2009.

[27] Zhang X， Ai J， Wang Z， et al. An efficient multi-dimensional index for cloud data management[C]// International CIKM Workshop on Cloud Data Management， Clouddb 2009， Hong Kong， China， November. DBLP， 2009：17-24.

[28] Wang J， Wu S， Gao H， et al. Indexing multi-dimensional data in a cloud system[C]// ACM SIGMOD International Conference on Management of Data. ACM， 2010：591-602.

[29] Tsatsanifos G， Sacharidis D， Sellis T. MIDAS： multi-attribute indexing for distributed architecture systems[C]// International Conference on Advances in Spatial and Temporal Databases. Springer-Verlag， 2011：168-185.

[30] 甘文婷. 大数据索引技术关键问题研究[D].湖北大学，2016.

[31] Abouzeid A， Bajda-Pawlikowski K， Abadi D， et al. HadoopDB： an architectural hybrid of MapReduce and DBMS technologies for analytical workloads[J]. Proceedings of the Vldb Endowment， 2009， 2（1）：922-933.

[32] Dittrich J， Quiané-Ruiz J A， Jindal A， et al. Hadoop++： making a yellow elephant run like a cheetah （without it even noticing）[J]. Proceedings of the Vldb Endowment， 2010， 3（1-2）：515-529.

[33] Dittrich J， Richter S， Schuh S， et al. Only aggressive elephants are fast elephants[J]. Proceedings of the Vldb Endowment， 2012， 5（11）：1591-1602.endprint