in Interview Questions
374 views
1 vote
1 vote
Define B tree and B+ tree. What’s the necessity? How does the search happen? Write the pseudo code and the recurrence relation.
in Interview Questions
374 views

1 Answer

1 vote
1 vote
it is used mainly for organzing large data in sorted order like table of a relaltion,e.g 1,00,000 employees table stored in a DATABASE.this table has lets say 10,000 blocks and finding for some data directly onto table on an averrgare requires 5000 block accesses.using B tree this can be reduced to log10,000 +1 block access in worst case for finding some record.now basic transfer unit is a block and block size is in range of 512 bytes.so using a BST will increase the height of tree and also will increase the space comeplexity,so more the branching less is the depth and in balaced  search tree it takes o(height)=o(log 10,000) .

now with higher degree the branching factor increases and height decreases so to be more precise its o(log 10,000/log(ORDER OF B TREE)

but order of a tree is constant.so aympototcally it wont recude disk block accesses but practically it does.
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true