data structures using step insert step insert figure tree applications of trees database is collection of related data the prime reason for using database is that it stores organized data to facilitate its users to updateretrieveand manage the data the data stored in the database may include namesaddressespicturesand numbers for examplea teacher may wish to maintain database of all the students that includes the namesroll numbersdate of birthand marks obtained by every student nowadaysdatabases are used in every industry to store hundreds of millions of records in the real worldit is not uncommon for database to store gigabytes and terabytes of data for examplea telecommunication company maintains customer billing database with more than billion rows that contains terabytes of data we know that primary memory is very expensive and is capable of storing very little data as compared to secondary memory devices like magnetic disks alsoram is volatile in nature and we cannot store all the data in primary memory we have no other option but to store data on secondary storage devices but accessing data from magnetic disks is , to , , times slower than accessing it from the main memory sob trees are often used to index the data and provide fast access consider situation in which we have to search an un-indexed and unsorted database that contains key values the worst case running time to perform this operation would be (nin contrastif the data in the database is indexed with treethe same search operation will run in (log nfor examplesearching for single key on set of one million keys will at most require , , comparisons but if the same data is indexed with tree of order then only comparisons will be required in the worst case hencewe see that indexing large amounts of data can provide significant boost to the performance of search operations when we use trees or generalized -way search treesthe value of or the order of trees is often very large typicallyit varies from - this means that single node in the tree can contain - keys and - pointers to child nodes we take large value of mainly because of three reasons disk access is very slow we should be able to fetch large amount of data in one disk access disk is block-oriented device that isdata is organized and retrieved in terms of blocks so while using tree (generalized -way search tree) large value of is used so that one single node of the tree can occupy the entire block in other wordsm represents the maximum number of data items that can be stored in single block is maximized to speed up processing more the data stored in blocklesser the time needed to move it into the main memory large value minimizes the height of the tree sosearch operation becomes really fast