Arpit's Newsletter read by 38000+ engineers
Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.
Relational Databases and some non-relational databases use B+ trees to hold the data but why?
One of the main reasons why SQL databases use B+ trees to hold the data is because of their efficiency in performing operations such as insert, update, find, and delete.
Before we delve into the details of why SQL databases use B+ trees, let’s first understand the limitations of storing data in a sequential file.
When records of a table are stored in one file sequentially, performing operations such as insert, update, and delete becomes complicated, with a complexity of O(n). The linear scan in the middle of the file for insertion or overriding can take up a lot of time and resources, making it inefficient.
In B+ trees, rows or documents of a table are clubbed in B+ tree nodes, and each node holds a maximum of some n
rows. For example, if one B+ tree node is 4KB big (same as a disk block size) and the row size is 40B, then each node will hold a maximum of 100 rows. This makes disk reads efficient since reading one node from a disk means reading 100 rows at once.
Non-leaf nodes in a B+ tree hold routing information, while leaf nodes hold the actual rows. The leaf nodes are linked so that linear traversal of the actual rows is possible. The B+ tree structure thus ensures that the table is always logically and physically arranged by its primary key
Finding a row by ID involves
Inserting a new row involves
Updating a row involves
Deleting a row involves
Range queries such as finding rows with IDs in the range of 100 to 600 involve finding the leaf node that holds the first row, traversing linearly to reach the row with ID 600, and extracting the data until then.
The B+ tree structure ensures that the time complexity of these operations is O(log n), which is much more efficient than the O(n) complexity of sequential file storage.
In conclusion, SQL databases use B+ trees to store data efficiently and perform operations such as insert, update, find, and delete with a time complexity of O(log n). This makes managing and storing large volumes of data more manageable and efficient.
Here's the video ⤵
Super practical courses, with a no-nonsense approach, are designed to spark engineering curiosity and help you ace your career.
An in-depth, self-paced, and on-demand course that for early engineers to become great at designing scalable, available, and extensible systems at scale.
A masterclass that helps experienced engineers become great at designing scalable, fault-tolerant, and highly available systems.
A course that helps covers Redis internals by reimplementing its core features like - event loop, serialization protocol, pipelining, eviction, and transactions.
Arpit's Newsletter read by 38000+ engineers
Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.