Notes
ADM: Ch. 3 (Dictionaries/Trees) & Ch. 12 (B-Trees)
Useful to read first the Ch. 2 of ADM first.
Dictionaries
Dictionaries are an ADT that allow us to access the values using keys
Primary Operations
As well as other data types, dictionaries allow us to:
- Add new items (Insertion(D,x))
- Delete an item (Deletion (D,x))
- Search an item (Search(D,k))
It also allow us to perform other types of operations, such as:
- Max(D)
- Min(D)
- Predecessor(D,x)
- Successor(D,x)
Dictionaries are particulary important in Database Engineering because they are the building blocks that support many important algorithms. Such as: Hash Tables, Self Balancing BSTs, B-Trees, B+Trees,LSM-Trees, etc
Then dictionaries can be implemented using different datatypes to take advantage of their features, in the following table is a comparison of how different implementations of dictionaries vary their computaional time complexity and which one represent and advantage depending of the purpose of the implementation
Analysis Computational Time Complexity worst case scenario for dictionary operation in different data structures
| Dictionary Operations | Array | Singly Linked List | Doubly Linked List | |||
|---|---|---|---|---|---|---|
| Unsorted | Sorted | Unsorted | Sorted | Unsorted | Sorted | Search (D,x) | O(n) | Olog(n) | O(n) | O(n) | O(n) | O(n) |
| Insert(D,x) | O(1) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Delete(D,x) | O(1)* | O(n) | O(n) O(1)* with sentinel |
O(n) O(1)* with sentinel |
O(1) | O(1) |
| Predecessor(D,x) | O(n) | O(1) | O(n) | O(n) | O(n) | O(1) |
| Successor(D,x) | O(n) | O(1) | O(n) | O(1) | O(n) | O(1) |
| Min(x) | O(n) | O(1) | O(n) | O(1) | O(n) | O(1) |
| Max(x) | O(n) | O(1) | O(n) | O(1) | O(n) | O(1) |
Hash tables
A hash table is a (randomized?) dictionary data structure that supports the INSERT, DELETE, and FIND operations in expected O(1) time. The core idea behind hash tables is to use a hash function that maps a large keyspace to a smaller domain of array indices, and then use constant-time array operations to store and retrieve the data. (read more)
Having the dictionary operations in a hash table being computed in O(1) is definitely an advantage in comparison with other datatypes, in modern database engineering, hash tables are indispensable primitives not necessarily as the primary disk storage index, but as the workhorse for in-memory operations like Grace Has Joins, Hash aggregations (Group by) and Transient Caching Layers While thinking about this the following question can arrive in mind:
But why not use only arrays if they are so intuitive to use at first glance and avoid ADT?
The problem can be disscused with different arguments but I will discuss the mathematical constraint and the Memory constraint reasons: Mathematically we will need an integer of K size as a key, thinking about modern 64-bit integer the key space universe U will spans 2^64 values imaging We have 1,000,000 rows N in our database that will let more than 99% unassigned, resulting in a catastrophic memory waste.
The memory constraint comes tangled with this issue and even if We have infinite memory and We dont care about the wasting, it will still need U space of contiguous slots of memory to define an array, if We define the this is impossible in modern computers, it will take 2^64 around 1.84 x 10^19 even in a smaller integer like 2^32 it will require gigabytes of space and the memory is fragmented (not every space in memory is taken continously) so it will be impossible to find a space slot of this dimmension.
This is solved by using a hash function that returns a fixed-size integer for a given input, this maintain the O(1) time complexity that We will have in a normal array making large amount of data easy searchable and inserted in the ADT.
Implementing a hash table
asdasdasd
asdasdasd
asdasdasd
asdasdasd
asdasdasd
Y.