面向多核CPU的高性能位图索引算法设计与实现.pdf

摘要

+

位图索引是一种常见的数据库索引技术。相比传统的Hash和B-tree索引结构，位图索

引可以提供更高的查询性能。因此，其被广泛应用在大型数据集的查询操作中，如科学数据

分析。然而，现有的位图索引技术存在两大问题。（1）应用程序并行化。摩尔定律的逐渐失

效使得程序向并行化方向发展，即同一数据结构被多个CPU核并行访问。这要求索引技术支

持并行的读写操作。（2）数据实时更新。当一个操作提交对数据的修改后，修改后的数据应

当被正确地保存并被其他操作所感知。同时，算法要保证更新前后数据库的一致性和正确性，

这要求对索引的修改必须被及时、正确地记录。当前的两大问题严重地阻碍了位图索引技术

的广泛应用。

因此，本文首先完成了对现有位图索引算法的并行化，并将这些算法运行在多核CPU上。

之后，本文分析了这些算法的潜在问题。基于此分析，本文提出了非阻塞、可更新的位图索

引算法（Non-blockingUpdatableBitmapindexing，NBUB）。相较之前并行化的算法，NBUB

是非阻塞的，即当系统有正在执行的读、写操作时，新到来的操作不会被阻塞。本文利用如

下技术实现了并发控制且获得了良好的性能表现。（1）多版本并发技术。该技术在系统中保

存了比特串的多个版本，同时系统使用全局的时间戳来标记这些版本的顺序。多版本技术分

离了读、写操作。当不同的读、写操作到来时，其仅需找到本操作对应的版本，而不受其他

操作影响。（2）事务技术。NBUB算法保证了数据库事务的ACID特性。在多版本的提交过

程中，算法使用两段锁解决了操作之间的冲突问题，同时提供检测机制解决了写偏序问题。

因此，NBUB提供了快照隔离的隔离等级。在算法的应用部分，本文将NBUB算法集成到

DBx1000数据库中，并将其应用到真实的科学数据分析中。实验结果表明，NBUB算法的吞

吐量约为UpBit的1.7倍、In-place的4.2倍、UCB的5倍。

关键词:位图索引，多版本并发控制，事务，并行算法，数据实时更新

Abstract

Bitmapindexingisacommondatabaseindexingtechnology.Comparedwithtraditionalindexes

+

suchasHashandB-tree,bitmapindexinghashigherqueryperformance.Therefore,ithasbeen

widelyusedinqueryinglargedatasetslikescientificdatasets.However,thecurrentbitmap

indexinghastwomajorproblems.(1)ApplicationParallelization.ThegradualfailureofMoores

lawleadstothedevelopmentofprogramsinthedirectionofparallelization.Thatis,thesamedata

structureissimultaneouslyaccessedbymultipleCPUcoresinparallel,whichrequiresindexingto

supportparallelreadandwriteoperations.(2)Real-timeDataUpdate.Whenanoperationupdates

data,itssubmissionshouldbecorrectlysavedandperceivedbyotheroperations.NBUBensuresthe

consistencyandcorrectnessofthedatabase