B-Tree Data Structure in Databases
How a Btree DS looks like:
DBs mostly use structured mappings like the Balanced Trees for quick operations, where
- Insertion and Search take O(log n) operations
- Each request is an I/O call
- An ACK is sent for each call
To optimize this, we can:
- Reduce the number of I/O calls via batch processing combined queries. which reduces the number of ACK responses as well.
- Use some other type of specialized data structure for R/W
Log based Data Structrues
- Log or append type structures such as Linked Lists has fastest write operations O(1) but slow reads O(logn)
- To overcome slow reads, sorted array can be used on "segments" where excess read operations does take place (i.e: building search indexes for these segments)
Alternatively, for making fast search operations to see whether data exists or not, use of Bloom Filters can be done, which can show whether a item exists.