Using prefix trees for searching text strings with disk-based storage
Ilya Taranov · DOAJ (DOAJ: Directory of Open Access Journals) · 2018
Searching and storing large amounts of text data is a common problem in computer science, though it have been discussed for a long time. We introduce data structure for searching a set of string values and storing it on disk efficiently which is used for indexing XML data in Sedna XML DBMS. This paper describes algorithms for insertion, deletion and searching of variable-length strings in disk-resident trie structures. We also compare our implementation with existent B-tree implementation and show that proposed data structure in some cases occupies several times less disk space than B-tree does with the same search efficiency.