btrees btree is variant of tree which stores sorted data in way that allows for efficient insertionretrievaland removal of recordseach of which is identified by key while tree can store both keys and records in its interior nodesa btreein contraststores all the records at the leaf level of the treeonly keys are stored in the interior nodes the leaf nodes of btree are often linked to one another in linked list this has an added advantage of making the queries simpler and more efficient typicallybtrees are used to store large amounts of data that cannot be stored in the main memory with btreesthe secondary storage (magnetic diskis used to store the leaf nodes of trees and the internal nodes of trees are stored in the main memory btrees store data only in the leaf nodes all other nodes (internal nodesare called index nodes or -nodes and store index values this allows us to traverse the tree from the root down to the leaf node that stores the desired data item figure shows btree of order figure btree of order many database systems are implemented using btree structure because of its simplicity since all the data appear in the leaf nodes and are orderedthe tree is always balanced and makes searching for data efficient btree can be thought of as multi-level index in which the leaves make up dense index and the non-leaf nodes make up sparse index the advantages of btrees can be given as follows records can be fetched in equal number of disk accesses it can be used to perform wide range of queries easily as leaves are linked to nodes at the upper level height of the tree is less and balanced supports both random and sequential access to records keys are used for indexing comparison between trees and btrees table shows the comparison between trees and btrees table comparison between trees and to btrees tree btree search keys are not repeated stores redundant search key data is stored in internal or leaf nodes data is stored only in leaf nodes searching takes more time as data may be found in leaf or non-leaf node searching data is very easy as the data can be found in leaf nodes only deletion of non-leaf nodes is very complicated deletion is very simple because data will be in the leaf node leaf nodes cannot be stored using linked lists leaf node data are ordered using sequential linked lists the structure and operations are complicated the structure and operations are simple