In-Memory Indexes Flashcards
(18 cards)
What differentiates T-Trees from Binary Trees?
- each node holds a set of keys and two pointers to child nodes
- every tree node has associated a min and max key
What is Cache Locality?
Programs tend to use data with addresses near or equal to those they have used recently
Temporal Locality
Recently referenced items are likely to be referenced again in the near future
Spatial Locality
Items with nearby addresses tend to be referenced close together in time
How is the cache organized?
- in cache lines (typically 64 Bytes)
- only load / evict full cache lines
Next-Line Prefetching
Read a, fetch a+1
Stream Prefetching
read a, a+1, fetch a+2, a+3
2 Tricks to improve cache friendlyness
- sequential access
- squeeze more useful data into a cacheline
What differentiates a CSS-Tree from a B+ Tree?
- fit each node into a cache line
- nodes are filled 100% with data
- eliminates all child pointers
Physical Representation of CSS Tree?
- contiguous array of nodes
- contiguous array of sorted data
Idea of CSB+ Tree
- nodes use one pointer to all children
- child nodes are stored in a node group
- node group pre-allocates space for inserts
Advantage of Locks
Guarantees isolation at tx level
Advantage of Latch
Protects critical section of the internal data structure from other threads
Latches on B+Trees
- acquire and release is needed when traversing the tree
- a thread can release a latch on parent node if its child node is considered safe
When is a B+ Node considered safe?
if it won’t split or merge on an update / delete
How to latch for B+ Search?
- acquire R latch on node and search node
- acquire R latch on child
- when child is latched, unlatch parent node
How to latch for B+ Insert / Delete?
- acquire W latch on node and search node
- acquire W latch on child
- once child is latched, check if it is safe
- if yes, release all locks on all ancestors
