B+ tree

Creating a B+ Tree_________________________________ : 

B+ Trees 1 Creating a B+ Tree_________________________________ C N G A H E K Q M F W L T Z D P R X Y S

Slide 2: 

B+ Trees 2 C N G A H E K Q M F W L T Z D P R X Y S G

Slide 3: 

B+ Trees 3 C N G A H E K Q M F W L T Z D P R X Y S G N

Slide 4: 

B+ Trees 4 C N G A H E K Q M F W L T Z D P R X Y S N

Slide 5: 

B+ Trees 5 C N G A H E K Q M F W L T Z D P R X Y S C N

Slide 6: 

B+ Trees 6 C N G A H E K Q M F W L T Z D P R X Y S

Slide 7: 

B+ Trees 7 C N G A H E K Q M F W L T Z D P R X Y S

Slide 8: 

B+ Trees 8 C N G A H E K Q M F W L T Z D P R X Y S

Slide 9: 

B+ Trees 9 C N G A H E K Q M F W L T Z D P R X Y S D (Split node)

Slide 10: 

B+ Trees 10 C N G A H E K Q M F W L T Z D P R X Y S (Split node) D

C N G A H E K Q M F W L T Z D P R X Y S : 

B+ Trees 11 C N G A H E K Q M F W L T Z D P R X Y S E A F C D G N T D K

C N G A H E K Q M F W L T Z D P R X Y S : 

B+ Trees 12 C N G A H E K Q M F W L T Z D P R X Y S E F A C D G N T K D Z

C N G A H E K Q M F W L T Z D P R X Y S : 

B+ Trees 13 C N G A H E K Q M F W L T Z D P R X Y S N T T W X Y X Z Right Sub-Tree

C N G A H E K Q M F W L T Z D P R X Y S : 

B+ Trees 14 C N G A H E K Q M F W L T Z D P R X Y S Right Sub-Tree N Q T W X Y T Z X S

Speed in B+ Tree Index : 

B+ Trees 15 Speed in B+ Tree Index In processing a query, we traverse a path from the root to a leaf node. If there are K search key values in the file, this path is no longer than log(n/2) K , where n is number of links possible in any given node. This means that the path is not long, even in large files. For a 4k byte disk block with a search-key size of 12 bytes and a disk pointer of 8 bytes, n is around 200. If n =100, a look-up of 1 million search-key values may take log50(1,000,000) = 4 nodes to be accessed. Since root is in usually in the buffer, so typically it takes only 3 or fewer disk reads.