it forms tree structure with the root at the top the index consists of -tree (balanced treestructure based on the values of the indexed column in this examplethe indexed column is name and the -tree is created using all the existing names that are the values of the indexed column the upper blocks of the tree contain index data pointing to the next lower blockthus forming hierarchical structure the lowest level blocksalso known as leaf blockscontain pointers to the data rows stored in the table if table has column that has many unique valuesthen the selectivity of that column is said to be high -tree indices are most suitable for highly selective columnsbut it causes sharp increase in the size when the indices contain concatenation of multiple columns the -tree structure has the following advantagessince the leaf nodes of -tree are at the same depthretrieval of any record from anywhere in the index takes approximately the same time -trees improve the performance of wide range of queries that either search value having an exact match or for value within specified range -trees provide fast and efficient algorithms to insertupdateand delete records that maintain the key order -trees perform well for small as well as large tables their performance does not degrade as the size of table grows -trees optimize costly disk access hashed indices in the last we discussed hashing in detail the same concept of hashing can be used to create hashed indices so farwe have studied that hashing is used to compute the address of record by using hash function on the search key value if at any point of timethe hashed values map to the same addressthen collision occurs and schemes to resolve these collisions are applied to generate new address choosing good hash function is critical to the success of this technique by good hash functionwe mean two things firsta good hash functionirrespective of the number of search keysgives an average-case lookup that is small constant secondthe function distributes records uniformly and randomly among the bucketswhere bucket is defined as unit of one or more records (typically disk blockcorrespondinglythe worst hash function is one that maps all the keys to the same bucket howeverthe drawback of using hashed indices includesthough the number of buckets is fixedthe number of files may grow with time if the number of buckets is too largestorage space is wasted if the number of buckets is too smallthere may be too many collisions it is recommended to set the number of buckets to twice the number of the search key values in the file this gives good space-performance tradeoff hashed file organization uses hashed indices hashing is used to calculate the address of disk block where the desired record is stored if is the set of all search key values and is the set of all bucket addressesthen hash function maps to we can perform the following operations in hashed file organization insertion to insert record that has ki as its search valueuse the hash function (kito compute the address of the bucket for that record if the bucket is freestore the record else use chaining to store the record