nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

The DCB-Tree: A Space-Efficient Delta Coded Cache Conscious B-Tree

verfasst von : Robert Binna, Dominic Pacher, Thomas Meindl, Günther Specht

Erschienen in: In Memory Data Management and Analysis

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Main-memory index structures have become mainstream for a large number of problem domains. However, in the case of web-based datasets, which feature exponential growth, it is an ongoing challenge to fit those data entirely in main-memory. In this paper, we present the DCB-Tree, an extremely space efficient main-memory index structure for the storage of short fixed-size keys. It features a two-stage cache-line aligned node layout. In comparison to other main-memory index structures it reduces the amount of memory required by 80 % in the best and by 30 % in the worst case. Although it is tailored towards space consumption, it features good overall performance characteristics. In particular, in the case of very large real world datasets it provides performance equal or superior to state of the art main-memory index structures.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Efficient Transaction Processing for Hyrise in Mixed Workload Environments

Nächstes Kapitel Composite Group-Keys

http://tinyurl.com/on8ccx3.

http://dbis-informatik.uibk.ac.at/static/ma/robert/imdm/imdm2014.zip.

http://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html.

http://www-db.in.tum.de/~leis/index/ART.tgz?lang=de.

http://docs.oracle.com/javase/8/docs/api/java/nio/ByteBuffer.html.

Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., Ives, Z.: DBpedia: a nucleus for a web of open data. In: Aberer, K., et al. (eds.) ISWC/ASWC 2007. LNCS, vol. 4825, pp. 722–735. Springer, Heidelberg (2007)CrossRef

Bayer, R.: Symmetric binary B-Trees: data structure and maintenance algorithms. Acta Informatica 1(4), 290–306 (1972)MathSciNetCrossRefMATH

Bayer, R., McCreight, E.: Organization and maintenance of large ordered indices. In: Proceedings of the SIGFIDET (now SIGMOD) 1970, p. 107. ACM Press, New York (1970)

Bayer, R., Unterauer, K.: Prefix B-Trees. ACM Trans. Database Syst. 2(1), 11–26 (1977)CrossRef

Binna, R., Gassler, W., Zangerle, E., Pacher, D., Specht, G.: SpiderStore: exploiting main memory for efficient RDF graph representation and fast querying. In: Proceedings of Workshop on Semantic Data Management (SemData) at VLDB (2010)

Bohannon, P., Mcllroy, P., Rastogi, R.: Main-memory index structures with fixed-size partial keys. In: Proceedings of SIGMOD 2001, vol. 30, pp. 163–174. ACM Press, New York, June 2001

Chen, S., Gibbons, P.B., Mowry, T.C., Valentin, G.: Fractal prefetching B+-Trees. In: Proceedings of SIGMOD 2002, p. 157. ACM Press, New York (2002)

Comer, D.: Ubiquitous B-Tree. ACM Comput. Surv. 11(2), 121–137 (1979)CrossRefMATH

Fredkin, E.: Trie memory. Commun. ACM 3(9), 490–499 (1960)CrossRef

10.

Gray, J.: Tape is dead, disk is tape, flash is disk, RAM locality is king, Gong Show Presentation at CIDR (2007)

11.

Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: 19th Annual Symposium on Foundations of Computer Science (SCFS 1978), pp. 8–21. IEEE, October 1978

12.

Hoffart, J., Suchanek, F.M., Berberich, K., Lewis-Kelham, E., de Melo, G., Weikum, G.: YAGO2: exploring and querying world knowledge in time, space, context, and many languages. In: Proceedings of WWW 2011, p. 229. ACM Press, New York (2011)

13.

Kim, C., Chhugani, J., Satish, N., Sedlar, E., Nguyen, A.D., Kaldewey, T., Lee, V.W., Brandt, S.A., Dubey, P.: FAST: fast architecture sensitive tree search on Modern CPUs and GPUs. In: Proceedings of SIGMOD 2010, p. 339 (2010)

14.

Lehman, T.J., Careay, M.J.: A study of index structures for main memory database management systems. In: Proceedings of VLDB 1986, pp. 294–303 (1986)

15.

Leis, V., Kemper, A., Neumann, T.: The adaptive radix tree: ARTful indexing for main-memory databases. In: Proceedings of ICDE 2013, pp. 38–49. IEEE, April 2013

16.

Levandoski, J.J., Lomet, D.B., Sengupta, S.: The Bw-tree: A B-tree for new hardware platforms. In: Proceedings of ICDE 2013, pp. 302–313 (2013)

17.

Mao, Y., Kohler, E., Morris, R.T.: Cache craftiness for fast multicore key-value storage. In: Proceedings of the 7th ACM European Conference on Computer Systems - EuroSys 2012, p. 183 (2012)

18.

Neumann, T., Weikum, G.: RDF-3X: a RISC-style engine for RDF. In: Proceedings of VLDB Endowment, vol. 1, pp. 647–659, August 2008

19.

Rao, J., Ross, K.A.: Cache Conscious Indexing for Decision-Support in Main Memory. In: Proceedings of VLDB 1999, pp. 475–486. Morgan Kaufmann Publishers Inc. (1999)

20.

Rao, J., Ross, K.A.: Making B+-Trees cache conscious in main memory. ACM SIGMOD Rec. 29(2), 475–486 (2000)CrossRef

21.

Schlegel, B., Gemulla, R., Lehner, W.: k-ary search on modern processors. In: Proceedings of the Fifth International Workshop on Data Management on New Hardware - DaMoN 2009, p. 52. ACM Press, New York (2009)

22.

Wulf, W.A., McKee, S.A.: Hitting the memory wall. ACM SIGARCH Comput. Archit. News 23(1), 20–24 (1995)CrossRef

Titel: The DCB-Tree: A Space-Efficient Delta Coded Cache Conscious B-Tree
verfasst von: Robert Binna
Dominic Pacher
Thomas Meindl
Günther Specht
Verlag: Springer International Publishing
Buch: In Memory Data Management and Analysis
Print ISBN: 978-3-319-13959-3

Electronic ISBN: 978-3-319-13960-9

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-13960-9_10

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner