is enough main memorythe bst is viable option for implementing both primary and secondary key indices unfortunatelythe bst can become unbalanced even under relatively good conditionsthe depth of leaf nodes can easily vary by factor of two this might not be significant concern when the tree is stored in main memory because the time required is still th(log nfor search and update when the tree is stored on diskhoweverthe depth of nodes in the tree becomes crucial every time bst node is visitedit is necessary to visit all nodes along the path from the root to each node on this path must be retrieved from disk each disk access returns block of information if node is on the same block as its parentthen the cost to find that node is trivial once its parent is in main memory thusit is desirable to keep subtrees together on the same block unfortunatelymany times node is not on the same block as its parent thuseach access to bst node could potentially require that another block to be read from disk using buffer pool to store multiple blocks in memory can mitigate disk access problems if bst accesses display good locality of reference but buffer pool cannot eliminate disk / entirely the problem becomes greater if the bst is unbalancedbecause nodes deep in the tree have the potential of causing many disk blocks to be read thusthere are two significant issues that must be addressed to have efficient search from disk-based bst the first is how to keep the tree balanced the second is how to arrange the nodes on blocks so as to keep the number of blocks encountered on any path from the root to the leaves at minimum we could select scheme for balancing the bst and allocating bst nodes to blocks in way that minimizes disk /oas illustrated by figure howevermaintaining such scheme in the face of insertions and deletions is difficult in particularthe tree should remain balanced when an update takes placebut doing so might require much reorganization each update should affect only disk few blocksor its cost will be too high as you can see from figure adopting rule such as requiring the bst to be complete can cause great deal of rearranging of data within the tree we can solve these problems by selecting another tree structure that automatically remains balanced after updatesand which is amenable to storing in blocks there are number of widely used balanced tree data structuresand there are also techniques for keeping bsts balanced examples are the avl and splay trees discussed in section as an alternativesection presents the - treewhich has the property that its leaves are always at the same level the main reason for discussing the - tree here in preference to the other balanced search trees is that