Parallel Processing of Multi-Directory Hashing

过去关于外部文件散列的研究的基本假设是，数据库驻留在磁盘上，记录在单处理器环境中处理。本文主要研究主存数据库中散列文件的并行处理。我们将关注一些基本的设计问题，特别是溢出桶的处理、主内存访问时间的限制、对数据库的并发访问以及处理器内存互连架构。一种称为多目录哈希的新哈希技术是本研究第一阶段的主要焦点。多目录散列是具有并行处理能力的可扩展散列的泛化。初步研究表明，多目录哈希可以达到主内存访问时间的下限，并保持接近100%的存储利用率。本研究的长期目标是：(1)开发可替代b树、数字搜索树和哈希的并行主存数据库算法；(2)开发和分析适合这些算法的处理器-存储器架构；(3)开发高效的并行主存数据库管理系统。

The basic assumption in past research on hashing for external files was that the database is disk-resident and the records are processed in a single processor environment. This work focuses on parallel processing of hashed files in main memory databases. We will focus on some fundamental design issues, particularly the handling of overflow buckets, bounds on the main memory access time, concurrent accesses to databases, and processor memory interconnection architecture. A new hashing technique called multi-directory hashing is the primary focus of the first phase of this research. Multi-directory hashing is a generalization of extendible hashing with parallel processing capability. Initial research shows that multi-directory hashing achieves the lower bound on main memory access time and maintains close to 100% storage utilization. The long range goals of this research are: (1) Develop algorithms for parallel main memory databases that are alternative to B-trees, digital search trees, and hashing; (2) Develop and analyze processor-memory architectures suitable for these algorithms; (3) Develop an efficient parallel main memory database management system.