B-tree indexes for high update rates

ABSTRACT

In some applications, data capture dominates query processing. For example, monitoring moving objects often requires more insertions and updates than queries. Data gathering using automated sensors often exhibits this imbalance. More generally, indexing streams is considered an unsolved problem.For those applications, B-tree indexes are good choices if some trade-off decisions are tilted towards optimization of updates rather than towards optimization of queries. This paper surveys some techniques that let B-trees sustain very high update rates, up to multiple orders of magnitude higher than traditional B-trees, at the expense of query processing performance. Not surprisingly, some of these techniques are reminiscent of those employed during index creation, index rebuild, etc., while other techniques are derived from well known technologies such as differential files and log-structured file systems.

REFERENCES

• 1: {A 96} Lars Arge: Efficient External-Memory Data Structures and Applications. University of Aarhus (Denmark), 1996.
• 2: Dave Anderson , Jim Dykes , Erik Riedel, More Than an Interface---SCSI vs. ATA, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 3: {AHV 02} Lars Arge, Klaus Hinrichs, Jan Vahrenhold, Jeffrey Scott Vitter: Efficient Bulk Operations on Dynamic R-Trees. Algorithmica 33(1): 104--128 (2002).
• 4: {G 03a} Goetz Graefe: Sorting and Indexing with Partitioned B-Trees. Conference on Innovative Data Systems Research, 2003.
• 5: {G 03b} Goetz Graefe: Partitioned B-trees - a user's guide. Datenbanksysteme für Business, Technologie und Web (BTW) 2003:668--671.
• 6: {G 04}Goetz Graefe: Write-Optimized B-Trees. VLDB Conference 2004: 672--683.
• 7: {GK 85} Dieter Gawlick, David Kinkade: Varieties of Concurrency Control in IMS/VS Fast Path. IEEE Data Eng. Bulletin 8(2): 3-10 (1985).
• 8: Andreas Gärtner , Alfons Kemper , Donald Kossmann , Bernhard Zeller, Efficient Bulk Deletes in Relational Databases, Proceedings of the 17th International Conference on Data Engineering, p.183-192, April 02-06, 2001
• 9: H. V. Jagadish , P. P. S. Narayan , S. Seshadri , S. Sudarshan , Rama Kanneganti, Incremental Organization for Data Recording and Warehousing, Proceedings of the 23rd International Conference on Very Large Data Bases, p.16-25, August 25-29, 1997
• 10: Harry Leslie , Rohit Jain , Dave Birdsall , Hedieh Yaghmai, Efficient Search of Multi-Dimensional B-Trees, Proceedings of the 21th International Conference on Very Large Data Bases, p.710-719, September 11-15, 1995
• 11: Peter Muth , Patrick O'Neil , Achim Pick , Gerhard Weikum, The LHAM log-structured history data access method, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.199-221, February 2000 [doi>10.1007/s007780050004]
• 12: Patrick O'Neil , Edward Cheng , Dieter Gawlick , Elizabeth O'Neil, The log-structured merge-tree (LSM-tree), Acta Informatica, v.33 n.4, p.351-385, 1996 [doi>10.1007/s002360050048]
• 13: John Ousterhout , Fred Douglis, Beating the I/O bottleneck: a case for log-structured file systems, ACM SIGOPS Operating Systems Review, v.23 n.1, p.11-28, Jan. 1989 [doi>10.1145/65762.65765]
• 14: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 15: Dennis G. Severance , Guy M. Lohman, Differential files: their application to the maintenance of large databases, ACM Transactions on Database Systems (TODS), v.1 n.3, p.256-267, Sept. 1976 [doi>10.1145/320473.320484]
• 16: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 17: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 18: Till Westmann , Donald Kossmann , Sven Helmer , Guido Moerkotte, The implementation and performance of compressed databases, ACM SIGMOD Record, v.29 n.3, p.55-67, Sept. 2000 [doi>10.1145/362084.362137]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Performance