Trees are not just limited and useful to solving your LeetCode questions, but they form the crux of most databases.
Every single variant of Tree is designed to be optimized for a certain class of operations and query pattern. A database typically has a subset of these implemented depending on the operations it supports.
Depending on the indexes you have created or the queries you fire, the database engine loads (or keeps data pre-loaded) in the right variant of the tree and executes the query. Some of the variants that are commonly found across databases are
- B-tree - range queries and equality searches on sorted data
- B+ tree - range queries over large datasets based on disk
- R-tree - spatial and multidimensional range queries
- T-tree - range queries with a high locality of reference
- Trie - prefix queries and auto-complete searches
- Suffix tree - substring queries and sequence matching
- Segment tree - Range queries and point updates in interval data
- Fenwick tree - Cumulative frequency table queries and prefix sum queries
- KD-tree - Multidimensional range queries in spatial and nearest neighbor queries
- Merkle tree - Verifying data integrity and content efficiently in distributed systems
- Quadtree: 2D spatial queries in geographic databases
- UB-tree - Multidimensional range queries in very large databases with high dimensional spaces
- M-tree - Metric space queries ex: nearest neighbor searches in distance-based data
So, if you have just started with Tree data structures, or if this post sparked some curiosity about them, try to build a deeper understanding of the trade-off each variant took. It will help you with building your first principles thinking.
⚡ I keep writing and sharing my practical experience and learnings every day, so if you resonate then follow along. I keep it no fluff.
youtube.com/c/ArpitBhayani