User:00Nexiom/B+ tree

Characteristics

• 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.
• 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.
• 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.

Algorithms

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.

B+ tree deletion

Applications

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.

iDistance

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.

Nonvolatile random-access memory (NVRAM) system

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.