Search Trees

Question 1

Ordered Data Sets

Answer 1

hashing stores items in random order
data should be ordered by key to support insert, remove, lookup
operations: lower bound, upper bound, range scan

Question 2

Standard Binary Search (arrays)

Answer 2

logn steps if array is sorted
0.5 branch misses per comparison on avg for random searches
access pattern is not cache friendly
on large arrays is slower than in B-tree

Question 3

Branch-Free Binary Search

Answer 3

conditional branch can be transformed to data dependency
no branch misses for small arrays

Question 4

Interpolation Search

Answer 4

assumes keys are uniformly distributed(distance between Elems is same/close to it) 10 13 15 26 28 30
a single, very large or very small outlier will destroy interpolation
can be combined with binary search

Question 5

Linear Search

Answer 5

O(n) steps
can be improved using SIMD instructions
good locality
array doesn’t have to be sorted for point search
best solution for small arrays

Question 6

Blocking Layout

Answer 6

store hot keys together in blocks
recursive structure
improves locality
allows use of SIMD instructions (k-ary search)

Question 7

Growing Arrays

Answer 7

better locality than linked lists
one downsize is growth because of limited size
standard approach: exponential growth plus copy

Question 8

Growing Arrays without Copying

Answer 8

64 pointers pointing to array of values
good locality

Question 9

Comparison-based Search Trees (binary search trees)

Answer 9

compare one elem at time
each comparison rules out half the elems (if tree is balanced)
log2n comparisons and height

Question 10

Binary Search Trees

Answer 10

each node stores one key/value pair and two child pointers
complex rebalancing logic
bad cache locality
pointer based: elem doesnt have to be moved physically during rebalancing

Adv:
if you insert an element, you just allocate a new entry and point into tree
if tree rebalanced: no need to copy, you just change pointer structure of the tree

Question 11

Skip List

Answer 11

elems in sorted linked list + additional shortcuts on top
probabilistic data structure (no worst case guarantees)
all items are stored in a sorted order by the key

Question 12

B+-tree

Answer 12

variant of B tree where inner nodes only store pointers, no values
leaf nodes are often chained to simplify range scan

Question 13

Sorted Arry

Answer 13

worst case for n elems:
lookup log2n
insert n

Question 14

Sorted Blocks of Fixed Size

Answer 14

split array into small sorted arrays of b elems, b is fixed

Question 15

Inner Nodes

Answer 15

indicate path to leaf node that has actual data
tree height: logb(n)
comparisons: log2n

Question 16

B-tree logic decomposition

Answer 16

two parts:
1. structure-modification operations (split, merge, new root) determine shape of B tree
2. per-node operations (lower bound, insert, delete, iterate) work on nodes locally
(2) can be changed without affecting high level logic (1)

Question 17

Physical Node Layouts

Answer 17

most common layout: array of sorted key/value pairs
binary search within each node
insert/delete moves half of elems on avg(to the right)

alternatives: store keys and values separately, unsorted leaf nodes but sorted immer nodes, encode binary search tree, trie or hash table within node

Question 18

what is the best node size?

Answer 18

in main memory, node size (b) can be freely chosen
node size should be at least cache line size
optimal page size for lookup is bigger that for inserts

Question 19

B trees with variable-length data

Answer 19

bad cache locality, because need ti dereference the pointer which generally will not be in cache
lots of memory allocation
memmory fragmentation from memory allocator

Question 20

Slotted page layout

Answer 20

enables variable-lenght data in sorted order
slots decouple logical from physical ordering
slots store offset and length

Question 21

Compaction

Answer 21

deletion in slotted page leaves holes
keep holes after deletion, but keep track of how many bytes are wasted
when running out of space, one can trigger compaction if its beneficial
best implemented by copying all keys to new empty page

Question 22

Separator Choice

Answer 22

when splitting node: choose shortest key around median as separator

Question 23

Suffix Truncation of Separator

Answer 23

keys in inner nodes are only used as signposts, do not have to be stored in leaf nodes
if separator is ABCDE and next key is AXYZ, separator can be truncated to AX

Question 24

Prefix Truncation, its difficulty

Answer 24

extract common prefix between smallest and largest key on node
on lookup, compare prefix first
speeds up comparison and saves space

issue: insertion of key may cause prefix to shrink -> all keys need to be enlarged, may not fit into node anymore, causing a split
solution: store fence keys on each page

Question 25

Fence keys for prefix truncation

Answer 25

use common prefix of fence keys
those are immutable after page was created by split and merge
can be stored on page or derived on demand

Question 26

key head in slot optimization

Answer 26

with slotted page layout, binary search requires loading key for every comparison
extract or copy first 4 bytes of key into slot

Question 27

Hints

Answer 27

extract a fixed number of equi-distant heads and store them consecutively

Question 28

Textbook merge (deletion and space management in b trees)

Answer 28

to avoid underfull nodes after deletion, one must merge or rebalance
if node is underfull (<50% fill factor):
find a neighboring node
if neighboring node has low enough fill factor:
merge two nodes into one, remove separator in parent, if parent is underfull merge parent the same way

else rebalance elems between two nodes

Question 29

B*tree

Answer 29

guarantees 66% fill factor.
insert and delete rebalance between 3 neighboring nodes

Question 30

Xmerge

Answer 30

insead of balancing during insert and delete, increase fill factor in background
if fill factor is low, merge X neighboring nodes into X-1 nodes

Question 31

B-tree: Cascading Insert

Answer 31

Scenario:
* leaf node is full, have to split and insert separator into parent
* parent is also full, have to split and insert separator into its parent
* repeat…
→ Insert can cascade upwards until a new root has to be created
Alternative: eager split
* when walking the tree during insert, split full inner nodes eagerly
* thus, when hitting the root node, the parent always has space
* simpler, can be faster, but average tree fill factor a bit lower

Question 32

why is a B-Tree usually faster than a binary tree

Answer 32

Instead of storing one key and having two children, B-tree nodes have n keys and n+1 children, where n can be large. This shortens the tree (in terms of height) and requires much less disk access than a binary search tree would.

Question 33

• in which scenario can binary search be slower than linear search?

Answer 33

if data is unsorted

Question 34

what data structure is a probabilistic alternative to a binary tree?

Answer 34

Skip lists

Question 35

• what is the main difference between a B+
  -Tree and a classical B-Tree?

Answer 35

insert and delete rebalance between 3 neighboring nodes

Question 36

• how many comparisons does binary search require on an array with N
  entries?

Answer 36

logN

Question 37

• how can you speed up lookup in a B-Tree?

Answer 37

link leaf nodes together, because range queries are faster