Implementing block-stored prefix trees in XML-DBMS.
The problem of search efficiency through large amount of text data is well-known problem in computer science. We would like to introduce a BST data structure that allows searches through a set of string values, and is optimized for reading and writing large blocks of data. This paper describes the algorithms for insertion, deletion and search of variable-length strings in diskresident trie structures. This data structure is used for value indexes on XML data. We also compare our implementation with existing B+ tree implementation and show that our structure occupies several times less space with the same search efficiency.Full text of the paper in pdf
Proceedings of SYRCoDIS'12: The Eighth Spring Researchers Colloquium on Databases and Information Systems, 2012, pp. 16-21.