Sunday, December 4, 2011

Variable length records and binary search?

why does indexing make it possible to perform a binary search on variable length records. when normally it is impossible to perform a binary search on variable length record file?|||a binary search works on the principle of the left node being smaller than the central node and the right node being larger than the central node..assuming the node i am searching for has the value 5 and the central node 2 levels up is 10





so 10 can have two child nodes right node =14,left node =7


7 can have two nodes =left node 5,right node 9








what an index on a record file of variable length would do is assign a unique id to each record in that file,so when the binary search is going on to find a specific node,it will have to follow the lesser path or greater than central node path..so to find the lesser part it will have to determine the position of the next node ..this is done by indexing since all it has to do is to reference that unique id which will point it to the next node and so on...








If the records are not indexed it will not be able to determine which node exists hence will fail|||Because the index tells you when each record begins.

No comments:

Post a Comment