Algorithm for Full-Text Indexing.

摘要

Conventional B-tree insertion algorithms typically require several disk accesses per insertion. This is inconveniently slow for full text databases. Group update can significantly speed up insertion. The idea is to collect and sort many keys in memory, and then merge them with the B-tree on disk. The paper presents a concurrent group update algorithm for B+-trees; in addition to allowing concurrent operation, the new algorithm provides 90% CPU time savings compared to existing group update algorithms. Experimental results show that the algorithm uses on the order of 0.003 disk accesses per key in full-text indexing.