Ivannikov Institute for System Programming of the RAS

Implementing block-stored prefix trees in XML-DBMS.


Borisenko O., Taranov I.


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.

Research Group

Information Systems

All publications during 2012 All publications