Storage engines are fundamental components of database systems responsible for data storage and retrieval. They implement various algorithms and data structures to efficiently manage the huge volumes of data. One crucial operation that storage engines must perform very efficiently is determining the absence of a key. In this article, we will explore the mechanisms and techniques used by storage engines to quickly ascertain that a key does not exist.

Hash Tables

Hash tables provide an efficient way of determining whether a key is present or not by using a hash function to compute the index in an array where the value is stored. A hash table performs operations in $O(1)$ time complexity on average. When a search is initiated, the hash function rapidly calculates the index for the key, and if that index in the hash table is empty or the key at the position does not match the searched key, the key is not present.

Example: A database utilizing a hash table for its storage engine would quickly ascertain the absence of a key by computing its hash, accessing the corresponding index, and confirming if the bucket is empty or contains a different key.

B-Trees and B+ Trees

B-Trees and B+ Trees are balanced tree data structures commonly used in databases and file systems. They maintain sorted data and allow searches, sequential access, insertions, and deletions in logarithmic time. To find a non-existent key, the tree is traversed from the root to the relevant leaf node. If the traversal path explicitly skips the location where the key would be (since keys are ordered), it confirms that the key does not exist.

Example: In a storage engine using a B+ Tree, checking for a non-existent key involves walking down the tree path. Each node provides pointers directing which child node to access next. If we reach a leaf node and the key is not among the keys, then it’s confirmed that the key does not exist.

Bloom Filters

Bloom filters are probabilistic data structures that tell whether an element might be in a set or definitely isn’t. They are exceptionally fast and space-efficient but suffer from false positives. A query returns either "possibly in set" or "definitely not in set." When applied in storage engines, Bloom filters are often used as a preliminary check before a more expensive lookup.

Example: Before checking the disk-based data structure (like SSTables in LSM-Trees used in LevelDB or Cassandra), the storage engine can check a Bloom filter. If the Bloom filter indicates the key is definitely not present, the engine can avoid the disk access entirely.

LSM Trees

Log-Structured Merge (LSM) Trees are used particularly in write-intensive scenarios. They write inserts, updates, and deletions to a memory-resident data structure (like a MemTable), and periodically merge these changes into the disk-based data structure. To determine the absence of a key, LSM Trees check both the in-memory structure and the on-disk structure. The presence of a key in neither confirms its absence.

Example: When looking for a non-existent key in an LSM Tree, the query first checks the MemTable. If not found, it subsequently checks the levels of SSTables, potentially assisted by Bloom filters to avoid unnecessary disk reads.

Summary Table

Conclusion

Determining the non-existence of a key efficiently is crucial for performance in database operations. Each storage engine utilizes specific data structures suited to their use case, balancing between speed, accuracy, and resource utilization. Depending on the operational requirements and data characteristics, a suitable storage mechanism is chosen to optimize for the most efficient way to determine that a key does not exist.