we can' assume that database table will alwaysor everbe sorted according to one field databases can have new records added and old records deleted at any time this is where the need for -tree comes from -tree is tree structure that is built over the topso to speakof database table to provide (log nlookup time to any record within the database table while the records themselves may be in any orderthe -tree provides the (log nsearch complexity into the table -tree is built by inserting records or items into the tree once builtthe index provides the efficient lookup of any record based on the key value stored in the -tree consider the code in sect lines - build the feed tbl index and lines - build the feedattribtype tbl index once builtthe indices are used when programming the query the loop beginning on line no longer contains two while loops to lookup the corresponding records in the two tables insteadthe -trees are consulted to find the corresponding records in the two tables when programmed this waythe query in sect runs in approximately sthree times faster than the originalnon-indexed query the sample query here uses relatively small tables imagine the speed up possible when either of the feed tbl or feedattribtype tbl tables contained millions of records in that casethe original query would not have completed in an acceptable amount of time while the indexed query given here would have completed in roughly the same amount of time or perhaps second longer at worst efficient join def main()select feed feednumfeed namefeedattribtype namefeedattribute value where feed feedid feedattribute feedid and feedattribute feedatribtypeid feedattribtype id attribtypecols ["int","char ","char ","int","int","int","int"feedcols ["int","int","int","char ","datetime","float","float","int","char ","int"feedattributecols ["int","int","float" feedattributetable open("feedattribute tbl"," " if os path isfile("feed idx")indexfile open("feed idx"," "feedtablereclength int(indexfile readline()feedindex eval(indexfile readline()elsefeedindex btree( feedtable open("feed tbl"," "offset for record in feedtablefeedid readfield(record,feedcols, anitem item(feedid,offsetfeedindex insert(anitemoffset+= feedtablereclength len(record print("feed table index created"indexfile open("feed idx"," "indexfile write(str(feedtablereclength)+"\ "indexfile write(repr(feedindex)+"\ "indexfile close( if os path isfile("feedattribtype idx")indexfile open("feedattribtype idx"," "this copy belongs to 'acha