varunu28

if (cache.containsKey(key)):
    return cache.get(key)
else:
    value = fetchFromDb(key)
    cache.put(key, value)
    return value

varunu28

/*
* Key of the map is zip code
* Value is a set of primary ids of record that have the zip code equal to key
*/
Map<Integer, Set<Integer>> zipCodeIndexToRecordIdMapping;

varunu28

BEGIN TRANSACTION
--- READ/WRITE OPERATIONS
COMMIT/ROLLBACK TRANSACTION;

varunu28

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashing {

    // Consistent Hashing with Ring having 50 buckets.
    final static int LIMIT = 50;

    // Sorted Map.
    final static SortedMap<Integer, String> bucketIdToServer = new TreeMap<>();

varunu28

1. Cache-Oblivious Algorithms and Data Structures - Erik Demaine (One of the earliest papers in cache oblivious data structures and algorithms that introduces the cache oblivious model in detail and examines static and dynamic cache oblivious data structures built between 2000-2003)

2. Cache Oblivious B-Trees - Bender, Demaine, Farch-Colton (This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. One of the fundamental papers in the field where both search trees discussed match the optimal search bound of Θ(1+log (B+1)N) memory transfers)

3. Cache Oblivious Search Trees via Binary Trees of Small Height - Brodal, Fagerberg, Jacob (The data structure discussed in this paper works on the version of [2] but avoids the use of weight balanced B-trees, and can be implemented as just a single

varunu28

Research Articles

1. Stratified B-trees and versioning dictionaries
2. A Comprehensive Performance Evaluation of Modern in-Memory Indices
3. FPGA-Accelerated Compactions for LSM-based Key-Value Store
4. Revisiting the design of LSM-tree Based OLTP storage engine with persistent memory
5. LB+Trees: optimizing persistent index performance on 3DXPoint memory
6. SLM-DB: Single-Level Key-Value Store with Persistent Memory - this inspired LotusDB

Percona / TokuDB

varunu28

import java.util.ArrayList;
import java.util.List;

public class MergeIntervals {

    public List<Interval> merge(List<Interval> intervalListOne, List<Interval> intervalListTwo) {
        List<Interval> mergedIntervals = new ArrayList<>();
        int idxOne = 0;
        int idxTwo = 0;
        int currIntervalStart = -1;