Fast string searching in secondary storage: theoretical developments and experimental results
Paolo Ferragina, Roberto Grossi · CINECA IRIS Institutial research information system (University of Pisa) · 1996
In a previous work, we proposed a text indexing data structure for secondary storage, which we called SB-tree, that combines the best of B-trees and suffix arrays, overcoming the limitations of inverted files, suffix arrays, suffix trees, and prefix B-trees. In this paper we study the performance of SB-trees in a practical setting, performing a set of searching and updating experiments. Improved performance was obtained by a new space efficient and alphabet-independent organization of the internal nodes of the SB-tree, and a new batch insertion procedure that avoids thrashing.