Open Access Open Access  Restricted Access Subscription or Fee Access

Recent Advancements in B-tree Based Data Structures

Nisha Sharma

Abstract


When many new keys need to be added to a B-tree, it is advantageous to insert them as a batch rather than individually, as it allows for all edges of the tree to be traversed only once instead of repeatedly traversing the path from the root to a leaf for each key. The information used for searching in the indexset is updated exclusively by a specialized maintenance process, which also takes care of maintaining the load factor of all levels in the tree structure. This load factor can be chosen freely and can differ between levels. When compared to Sagiv's method, it is clear that this approach provides additional benefits. Additionally, this approach can be more easily scaled to handle larger data volumes or more complex data structures, since the maintenance process can be optimized independently of the normal data processing pipeline. Overall, the use of a specialized maintenance process for updating the search index-set and load factor in a tree structure offers numerous benefits for improving the efficiency, reliability, and scalability of data retrieval operations.


Full Text:

PDF

References


S Levy AY, Mumick IS, Sagiv Y. Query optimization by predicate move-around. In VLDB. 1994 Sep 12; 96–107.

Chaudhuri S, Shim K. Including group-by in query optimization. Proceedings of the 20th VLDB Conference Santiago, Chile, 1994. p. 354-66.

Ferragina P, Lillo F, Vinciguerra G. On the performance of learned data structures. Theor Comput Sci. 2021 Jun 6;871:107-20. doi: 10.1016/j.tcs.2021.04.015.

Mostafa SA. A case study on B-tree database indexing technique. J Soft Comput Data Min. 2020 Mar 4;1(1):27-35.

Paul J, Lu S, He B. Database systems on GPUs. FNT in Databases. 2021 Jul 19;11(1):1-108. doi: 10.1561/1900000076.

Guo Q, Zhang J, Guo S, Ye Z, Deng H, Hou X et al. Urban tree classification based on object-oriented approach and random forest algorithm using unmanned aerial vehicle (UAV) multispectral imagery. Remote Sens. 2022 Aug 11;14(16):3885. doi: 10.3390/rs14163885.

Abdullah A, Zhuge Q. The Comparison Between T*_Tree And B+_Tree On Modern Hardware Revisited. 2nd Joint International Information Technology, Mechanical and Electronic Engineering Conference (JIMEC 2017) 2017 Oct (pp. 81-4). Atlantis Press. doi: 10.2991/jimec-17.2017.17.

Wu S, Jiang D, Ooi BC, Wu KL. Efficient B-tree based indexing for cloud data processing. Proc VLDB Endow. 2010 Sep 1;3(1-2):1207-18. doi: 10.14778/1920841.1920991.

Li Y, He B, Yang RJ, Luo Q, Yi K. Tree indexing on solid state drives. Proc VLDB Endow. 2010 Sep 1;3(1-2):1195-206. doi: 10.14778/1920841.1920990.

Brefeld U, Fromont E, Hotho A, Knobbe A, Maathuis M, Robardet C, editors. Machine learning and knowledge discovery in databases. European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part II. Switzerland AG: Springer Nature; 2020. doi: 10.1007/978-3-030-46147-8.


Refbacks

  • There are currently no refbacks.