-trees the advantages of -trees -tree may contain entire records instead of just key/value pairs as appear in fig where the key/value pairs are the feedid and record number of each record in the feed table for instancethe entire record for feedid might be stored directly in the -tree where ( , currently appears in the examples in this text the -tree and the database table are stored separately this has the advantage that more than one -tree index could be built over the feed table the -tree in fig is built over the feedid field some other unique field might be used to build another -tree over the table if desired by storing the -tree and the table separatelymultiple indices are possible as mentioned earlier in the -trees provide (logd nlookup time where is the degree of the -tree and is the number of items in the tree hash tables provide faster lookup time than -tree so why not use hash table insteadunlike hash tablea -tree provides ordered sequential access to the index you can iterate over the items in -tree much like binary trees provide iteration iteration over -tree provides the items or keys in ascending (or descendingorder hash table does not provide an ordering of its keys -trees provide (log ninsertdeleteand lookup time as well while not as efficient as hash tables in this regardb-trees nodes are often quite large providing very flat tree in this casethe time for these three operations often comes close to that of hash table -trees are often constructed with literally millions of items when -tree reaches this sizeholding all the nodes in memory at one time may consume lot of ram this is great advantage of -trees over hash tables -tree may be stored in file itself since files are randomly accessible on diska -tree' node may be thought of as record in file consider the -tree in fig the nodes and could be thought of as three records within file the record number are the pointer valuesso to search the -tree it is only necessary to start with the root node in memory thento search when pointer is followed during searchthe record corresponding to the new node is read into memory during the search search can proceed in this wayreading one record at time from disk typically pool of records would be held in memory for -tree and records would be replaced in memory using some sort of node replacement scheme in this way fixed amount of ram can be allocated to hold -tree that would typically be much smaller than the total size of the tree in additionsince -tree can be stored in fileit is not necessary to reconstruct the -tree each time it is needed the code in sect stores the -trees in two files named feed idx and feedattribtype idx and reads the index from the file the next time the program is run deleting record from table with million records or more in it could be an expensive operation if the table has to be completely rewritten if sequential access to the underlying table is handled through the -tree or if the entire file is stored in the nodes of the -treedeletion of row or record in the table gets much simpler for instancein fig the feed with feedid of remains in the feed tbl filebut this copy belongs to 'acha