• #08 - Tree Indexes: B+Trees (CMU Intro to Database Systems)

• SQLite: How it works

• Write a database from scratch

• Understanding B-Trees: The Data Structure Behind Modern Databases

• Build a NoSQL Database From Scratch in 1000 Lines of Code

• Writing a SQL database from scratch in Go: 1. SELECT, INSERT, CREATE and a REPL

• Database Engine Development

• https://github.com/cmu-db/bustub

1. Persistence. How not to lose or corrupt your data. Recovering from a crash.
2. Indexing. Efficiently querying and manipulating your data. (B-tree).
3. Concurrency. How to handle multiple (large number of ) clients. And transactions.

Vector Db

• https://github.com/skyzh/write-you-a-vector-db

Search

• The Art of Searching

• Algorithms & data-structures that power Lucene & ElasticSearch

• How do Spell Checkers work? Levenshtein Edit Distance

• The Algorithm Behind Spell Checkers

Data Structure

• Heaps, heapsort, and priority queues - Inside code
• Trie data structure - Inside code
• Compressed trie

Probablistic Data structures

• Hello Interview : Bloom Filters, Count-Min Sketch, HyperLogLog

• Probablistic data structure lectures

Bloom filter

• Wikipedia
• mCoding : Bloom Filters
• Number0 : Bloom Filters
• ByteByteGo : Bloom Filters
• Spanning Tree : What Are Bloom Filters?
• ByteMonk : Bloom Filters

Bloom filter is a space-efficient probabilistic data structure, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not - in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed.

A Bloom filter is a representation of a set of n items, where the main requirement is to make membership queries; i.e., whether an item is a member of a set.

Uses

Cache filtering

Content delivery networks deploy web caches around the world to cache and serve web content to users with greater performance and reliability. A key application of Bloom filters is their use in efficiently determining which web objects to store in these web caches. To prevent caching one-hit-wonders, a Bloom filter is used to keep track of all URLs that are accessed by users.

Web Crawler

HyperLogLog

• Wikipedia
• PapersWeLove : HyperLogLog
• The Algorithm with the Best Name - HyperLogLog Explained
• A problem so hard even Google relies on Random Chance
• Counting BILLIONS with Just Kilobytes
• https://github.com/tylertreat/BoomFilters/blob/master/hyperloglog.go

HyperLogLog is an algorithm for the count-distinct problem, Probabilistic cardinality estimators.

Count–min sketch

• Wikepedia
• https://github.com/tylertreat/BoomFilters/blob/master/countmin.go
• Count-min Sketch

The goal of the basic version of the count–min sketch is to consume a stream of events, one at a time, and count the frequency of the different types of events in the stream.

HeavyKeeper TopK

• Understanding Probabilistic Data Structures

TDigest

• Sketching Data with T Digest

Cache

• TinyLFU: A Highly Efficient Cache Admission Policy

• Caffeine Design of a Modern Cache

• Design of a Modern Cache

• The State of Caching in Go

• Introducing Ristretto: A High-Performance Go Cache

• On Window TinyLFU

• https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU

• https://github.com/hypermodeinc/ristretto

• https://github.com/dgryski/go-tinylfu

LSM-Tree

#04 - Database Storage: Log-Structured Merge Trees & Tuples (CMU Intro to Database Systems)

https://github.com/facebook/rocksdb/wiki

https://github.com/krasun/lsmtree https://github.com/skyzh/mini-lsm

OLAP

• https://github.com/risinglightdb/risinglight

Concurrency

• Golang concurrency - Locks, Lock Free and everything in between

• Optimistic Locking clearly explained

• Understanding the Disruptor

• https://en.wikipedia.org/wiki/Actor_model

• The Art of Multiprocessor Programming

• Seven Concurrency Models in Seven Weeks

• https://proto.actor/docs/

• The Actor Model

• A brief introduction to the actor model & distributed actors

• Introduction to the Actor Model for Concurrent Computation

• https://github.com/vladopajic/go-actor

• https://www.brianstorti.com/the-actor-model/

• Code : Ring Buffer

• https://kmdreko.github.io/posts/20191003/a-simple-lock-free-ring-buffer/

• Producer/Consumer, The RingBuffer and The Log

• Disruptor

• https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Articles

• https://github.com/smarty-prototypes/go-disruptor

Compress

• Data Encodings used by Columnar and Time series databases