Formulae for B-tree and B⁺-tree in DB

A B-tree and a B⁺-tree where p’s are pointers to nodes, k’s are keys and a’s are addresses for the data

The formula for B-tree

The formula for B-tree

The formula for B⁺-tree

The formula for internal nodes of the B⁺-tree
The formula for the leaves of the B⁺-tree with the next pointer

Example for B-tree

Table with the formulae for the number of entries

Example for B⁺-tree

The order for the internal nodes
The order for the leaves
Table with the formulae for the number of entries, B⁺-tree height 2

References

  1. Wikipedia. B-tree, B⁺-tree.
  2. Fundamentals of Database Systems. 7th edition. Ramez Elmasri, Shamkant B. Navathe. ch 16–17.
  3. The Ubiquitous B-Tree. Douglas Comer, 1979. Link.

 by the author.

--

--

--

Too lazy to open up a blog

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Jupyter notebooks for iPad

Embed code not available

Weeknotes S5 ep03: Stop leaving glass bottles on dry grass

Docker Architecture and it’s component

10 Handy Spring Batch Tricks

InvArch Weekly Wednesday: March 23rd, 2022

On Data Engineering code reviews

Is GraphQL the new REST ?

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Gianluca

Gianluca

Too lazy to open up a blog

More from Medium

Cassandra DB — What you should know!

Dimensionality in Dynamic Programming

The Main Search and Sort Algorithms

Concurrent and simple data structure