What are the differences between B trees and B trees

Question

In a b-tree you can store both keys and data in the internal and leaf nodes  but in a b  tree you have to store the data in the leaf nodes only  Is there any advantage of doing the above in a b  tree  Why not use b-trees instead of b  trees everywhere  as intuitively they seem much faster  I mean  why do you need to replicate the key  data  in a b  tree

User · Answer

The major drawback of B-Tree is the difficulty of Traversing the keys   sequentially  The B  Tree retains the rapid random access property of   the B-Tree while also allowing rapid sequential access      ref  Data Structures Using C   Author   Aaro M Tenenbaum  http   books google co in books id X0Cd1Pr2W0gC amp pg PA456 amp lpg PA456 amp dq drawback of B-Tree is the difficulty of Traversing the keys sequentially amp source bl amp ots pGcPQSEJMS amp sig F9MY7zEXYAMVKl Sg4W-0LTRor8 amp hl en amp sa X amp ei nD5AUbeeH4zwrQe12oCYAQ amp ved 0CDsQ6AEwAg v onepage amp q drawback 20of 20B-Tree 20is 20the 20difficulty 20of 20Traversing 20the 20keys 20sequentially amp f false

User · Answer

The image below helps show the differences between B  trees and B trees   Advantages of B  trees    Because B  trees don t have data associated with interior nodes  more keys can fit on a page of memory  Therefore  it will require fewer cache misses in order to access data that is on a leaf node  The leaf nodes of B  trees are linked  so doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes  A B tree  on the other hand  would require a traversal of every level in the tree  This full-tree traversal will likely involve more cache misses than the linear traversal of B  leaves    Advantage of B trees    Because B trees contain data with each key  frequently accessed nodes can lie closer to the root  and therefore can be accessed more quickly

User · Answer

In B  Tree  since only pointers are stored in the internal nodes  their size becomes significantly smaller than the internal nodes of B tree  which store both data key   Hence  the indexes of the B  tree can be fetched from the external storage in a single disk read  processed to find the location of the target  If it has been a B tree  a disk read is required for each and every decision making process  Hope I made my point clear

User · Answer

A B tree is a balanced tree in which every path from the root of the tree to a leaf is of the same length  and each nonleaf node of the tree has between  n 2  and  n  children  where n is fixed for a particular tree  It contains index pages and data pages  Binary trees only have two children per parent node  B  trees can have a variable number of children for each parent node

User · Answer

Take one example - you have a table with huge data per row  That means every instance of the object is Big   If you use B tree here then most of the time is spent scanning the pages with data - which is of no use  In databases that is the reason of using B  Trees to avoid scanning object data   B  Trees separate keys from data    But if your data size is less then you can store them with key which is what B tree does

User · Answer

B  Trees are especially good in block-based storage  eg  hard disk   with this in mind  you get several advantages  for example  from the top of my head      high fanout   low depth  that means you have to get less blocks to get to the data   with data intermingled with the pointers  each read gets less pointers  so you need more seeks to get to the data simple and consistent block storage  an inner node has N pointers  nothing else  a leaf node has data  nothing else   that makes it easy to parse  debug and even reconstruct  high key density means the top nodes are almost certainly on cache  in many cases all inner nodes get quickly cached  so only the data access has to go to disk

User · Answer

The primary distinction between B-tree and B tree is that B-tree eliminates the redundant storage of search key values Since search keys are not repeated in the B-tree we may not be able to store the index using fewer tree nodes than in corresponding B tree index However since search key that appear in non-leaf nodes appear nowhere else in B-tree we are forced to include an additional pointer field for each search key in a non-leaf node  Their are space advantages for B-tree  as repetition does not occur and can be used for large indices

User · Answer

Adegoke A  Amit  I guess one crucial point you people are missing is difference between data and pointers as explained in this section   Pointer   pointer to other nodes   Data  - In context of database indexes  data is just another pointer to real data  row  which reside somewhere else   Hence in case of B tree each node has three information keys  pointers to data associated with the keys and pointer to child nodes   In B  tree internal node keep keys and pointers to child node while leaf node keep keys and pointers to associated data  This allows more number of key for a given size of node  Size of node is determined mainly by block size    Advantage of having more key per node is explained well above so I will save my typing effort

User · Answer

One possible use of B  trees is that it is suitable for situations  where the tree grows so large that it does not fit into available  memory  Thus  you d generally expect to be doing multiple I O s  It does often happen that a B  tree is used even when it in fact fits into  memory  and then your cache manager might keep it there permanently  But  this is a special case  not the general one  and caching policy is a  separate from B  tree maintenance as such   Also  in a B  tree  the leaf pages are linked together in a linked list  or doubly-linked list   which optimizes traversals  for range searches  sorting  etc     So the number of pointers is a function of the specific algorithm that is used

User · Answer

B Trees are much easier and higher performing to do a full scan  as in look at every piece of data that the tree indexes  since the terminal nodes form a linked list   To do a full scan with a B-Tree you need to do a full tree traversal to find all the data   B-Trees on the other hand can be faster when you do a seek  looking for a specific piece of data by key  especially when the tree resides in RAM or other non-block storage   Since you can elevate commonly used nodes in the tree there are less comparisons required to get to the data

User · Answer

Example from Database system concepts  5th   B -tree   corresponding B-tree

User · Answer

In a B tree search keys and data are stored in internal or leaf nodes  But in a B -tree data is stored only in leaf nodes  Full scan of a B  tree is very easy because all data are found in leaf nodes  Full scan of a B tree requires a full traversal  In a B tree  data may be found in leaf nodes or internal nodes  Deletion of internal nodes is very complicated  In a B  tree  data is only found in leaf nodes  Deletion of leaf nodes is easy    Insertion in B tree is more complicated than B  tree   B  trees store redundant search keys but B tree has no redundant value  In a B  tree  leaf node data is ordered as a sequential linked list but in a B tree the leaf node cannot be stored using a linked list  Many database systems  implementations prefer the structural simplicity of a B  tree

User · Answer

The principal advantage of B  trees over B trees is they allow you to pack in more pointers to other nodes by removing pointers to data  thus increasing the fanout and potentially decreasing the depth of the tree   The disadvantage is that there are no early outs when you might have found a match in an internal node   But since both data structures have huge fanouts  the vast majority of your matches will be on leaf nodes anyway  making on average the B  tree more efficient

User · Answer

Define  much faster    Asymptotically they re about the same   The differences lie in how they make use of secondary storage   The Wikipedia articles on B-trees and B trees look pretty trustworthy

[database] What are the differences between B trees and B+ trees?

Examples related to database

Examples related to data-structures