User:00Nexiom/B+ tree
 | This is the sandbox page where you will draft your initial Wikipedia contribution.
If you're starting a new article, you can develop it here until it's ready to go live. If you're working on improvements to an existing article, copy only one section at a time of the article to this sandbox to work on, and be sure to use an edit summary linking to the article you copied from. Do not copy over the entire article. You can find additional instructions here. Remember to save your work regularly using the "Publish page" button. (It just means 'save'; it will still be in the sandbox.) You can add bold formatting to your additions to differentiate them from existing content. |
Characteristics
[edit]- The B+ tree structure expands/contracts as the number of records increases/decreases. There are no restrictions on the size of B+ trees. Thus, increasing usability of a database system.
- Any change in structure does not affect performance due to balanced tree properties. [1]
- The data is stored in the leaf nodes and more branching of internal nodes helps to reduce the tree's height, thus, reduce search time. As a result, it works well in secondary storage devices.[2]
- Searching becomes extremely simple because all records are stored only in the leaf node and are sorted sequentially in the linked list.
- We can retrieve range retrieval or partial retrieval using B+ tree. This is made easier and faster by traversing the tree structure. This feature makes B+ tree structure applied in many search methods.[1]
Algorithms
[edit]The basic of delete algorithm is to remove the desire entry node from the tree structure. We recursively calling the delete algorithm to the appropriate nodes until no node is found. For each function calling, we traverse along, using the index to navigate until finding that node, remove, and then work back up to the root.
At entry L that we wish to remove:
- If L is at least half-full, done
- If L has only d-1 entries, try to re-distribute, borrowing from sibling (adjacent node with same parent as L).
After the re-distribution of two sibling nodes happen, the parent node must be updated to reflect this change. The index key that points to the second sibling must take the smallest value of that node to be the index key.
- If re-distribute fails, merge L and sibling. After merging, the parent node is updated by deleting the index key that point to the deleted entry. In other words, if merge occurred, must delete entry (pointing to L or sibling) from parent of L.
Note: merge could propagate to node, which means decreasing height.[3]
Applications
[edit]Finding objects in a high-dimensional database that are comparable to a particular query object is one of the most often utilized and yet expensive procedures in these systems. In such situations, finding the closest neighbor using a B+ tree is productive.[4]
B+ tree is efficiently used to construct an indexed search method called iDistance. iDistance searches for k nearest neighbors (kNN) in high-dimension metric spaces. The data in those high-dimension spaces is divided based on space or partition strategies, and each partition has an index value that is close with the respect to the partition. From here, those points can be efficiently implemented using B+ tree, thus, the queries are mapped to single dimensions ranged search. In other words, the iDistance technique can be viewed as a way of accelerating the sequential scan. Instead of scanning records from the beginning to the end of the data file, the iDistance starts the scan from spots where the nearest neighbors can be obtained early with a very high probability.[5]
Nonvolatile random-access memory (NVRAM) has been using B+ tree structure as the main memory access technique for the Internet Of Things (IoT) system because of its non static power consumption and high solidity of cell memory. B+ can regulate the trafficking of data to memory efficiently. Moreover, with advanced strategies on frequencies of some highly used leaf or reference point, the B+ tree shows significant results in increasing the endurance of database systems.[6]
References
[edit]- ^ a b "Scalable Splitting of Massive Data Streams". Database Systems for Advanced Applications.
- ^ [Database Systems for Advanced Applications "Update Migration: An Efficient B+ Tree for Flash Storage"]. Lecture Notes in Computer Science, vol 5982. Springer, Berlin, Heidelberg.
{{cite journal}}: Check|url=value (help) - ^ Ramakrishnan, Raghu (2003). Database management systems. Johannes Gehrke (3rd ed ed.). Boston: McGraw-Hill. ISBN 0-07-246563-8. OCLC 49977005.
{{cite book}}:|edition=has extra text (help) - ^ Database Systems for Advanced Applications. Japan. 2010.
{{cite book}}: CS1 maint: location missing publisher (link) - ^ Jagadish, H. V.; Ooi, Beng Chin; Tan, Kian-Lee; Yu, Cui; Zhang, Rui (2005-06). "iDistance: An adaptive B + -tree based indexing method for nearest neighbor search". ACM Transactions on Database Systems. 30 (2): 364–397. doi:10.1145/1071610.1071612. ISSN 0362-5915.
{{cite journal}}: Check date values in:|date=(help) - ^ Dharamjeet; Chen, Tseng-Yi; Chang, Yuan-Hao; Wu, Chun-Feng; Lee, Chi-Heng; Shih, Wei-Kuan (2021-12). "Beyond Write-Reduction Consideration: A Wear-Leveling-Enabled B⁺-Tree Indexing Scheme Over an NVRAM-Based Architecture". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 40 (12): 2455–2466. doi:10.1109/TCAD.2021.3049677. ISSN 0278-0070.
{{cite journal}}: Check date values in:|date=(help)