SSTable is a data structure that stores key-  value pairs in an ordered format  optimized for efficient reads and disk  storage.

It introduces a new requirement to  segment files: it requires that the content  of the segments was sorted.

Each key only appears once within each  merged segment file (compaction already  ensures that).

We need a new kind of compact operation:  merge and sort. Merge and sort  complexity: O(n * log n).


Using SSTables we don't need to keep a  complete key index in memory (sparse  index).

We can use an in-memory sparse index  with one key per segment to locate other  keys by scanning from nearby offsets.

Example: a key like handiwork, when you  know the offsets for the keys handback  and handsome, you know handiwork must  appear between those two. You can jump  to the offset for handback and scan from  there until you find handiwork, if not, the  key is not present.


With this we solve the range query.

Maintaining a sorted structure on disk is  possible, but it's much easier to manage  in memory using tree data structures like  red-black or AVL trees.

Records can be grouped in segments and  compressed before being written to disk,  which enhances storage efficiency during  read requests.

Compaction and merging process is  carried out time to time, or when the  system detects two identical keys in two  different segments.

A memtable is an in-memory (usually a  tree), sorted, mutable data structure  used to keep a segments of an SSTable.

When a write comes in, add it to an in-memory	balanced	tree	structure (memtable)
When the memtable gets bigger than  some threshold (megabytes), write it  out to disk as an SSTable file. Writes can	continue	to	a	new	memtable instance.
On a read request, try to find the key in  the memtable, then in the most recent  on-disk segment, then in the next-older  segment, etc.

What Happens if a database using  a Memcached structure crashes?

o The	most	recent	writes	are  lost...


To avoid losing information, we can Keep a Write  Ahead Log (WAL) file in disk with same info than  memtable.
That log is not in sorted order, but that doesn't matter,  because its only purpose is to restore the memtable  after crash.
Every time the memtable is written out to an SSTable,  the log can be discarded.
When system fails:
Rebuild memtable from log file (slow but safe).
Must add all keys and values.
Expected to be used only in emergencies (not  often).


LSM Trees are a data structure used  in NoSQL databases to efficiently  manage large data volumes. They are  designed to optimize performance in  systems that handle high rates of  data insertion and updates.
It organizes the data into layers of  sorted structures, each with more  and more compressed data.
The top layer is the fastest to access  but the least compressed. As the data  piles up, it’s compressed and written  into a new SSTable.
We can decide how many layers we  need and how much compression to  apply.


It	is	composed	of	the	following elements:
- Memtable: is an in-memory, sorted mutable data structure that contain a  SStable. When data is written to LSM  Trees, it’s first written to the Memtable.

SSTables: are the heart of the LSM  Tree. They store data in sorted order,  enabling efficient queries and range  scans. Each SSTable represents a  snapshot of data at a specific point in  time. They are immutable.

Bloom Filter: is a data structure that  tells the LSM Tree whether the data  exists or not at some level of the  sstables.

Levels:	To	manage	data	efficiently SSTables are organized into levels.  Lower levels contain more recent  data, while higher levels store compacted data. This hierarchical approach balances read and write performance, preventing bottlenecks.

Write Ahead Log (WAL): is an append  only log that provides durability in the  database. When the data is written to  the memtable it is concurrently written  to the WAL. The log acts as a safety  net for the database, logging every  operation that takes place in case of  any system failures.

Write new value: (doily, 42)

The data is first written to the in-memory  layer (memcache) for speedy performance.

Simultaneously, the changes are recorded  in the Write-Ahead Log to ensure data  integrity.

Then, at regular intervals or when the in-  memory layer reaches a certain threshold,  the data is flushed to disk and organized  into SSTables.


Read new key: (handicap)

Check the memtable. If the key is  not in memtable:
First: search in the Bloom Filter  to know the level and the  sstable where the data is stored.

Second: search for the key in  sparse in-memory index to find  the SSTable block that contains  the key.

Third: scan a segment file to  find the key.

Example: find dollar (not in  memtable)

Search in the Bloom Filter in  which sstable is the dollar  key.

Search in the sparse index of  the sstable in which segment  is dollar. It comes between  dog and downgrade.

Scan from offset 17208 to  19504 to find the value.


B-tree (Balanced Tree) is a data structure  that provides sorted data and allows  searches, sequential access, attachments  and removals in sorted order.
The B-tree simplifies the binary search  tree by allowing nodes with more than  two children.
Their design is optimized to minimize the  number of disk accesses, making them  very efficient for read operations.
B-trees break the database down into  fixed-size blocks or pages, traditionally  4KB.
They can be uses both in relational and  NonSql databases.


To update the value for an existing key  in a B-tree, you search for the leaf page  containing that key, change the value in  that page, and write the page back to  disk (any references to that page remain  valid).


To add a new key, you need to find the  page whose range encompasses the new  key and add it to that page. If there isn’t  enough free space in the page to  accommodate the new key, it is split  into two half-full pages, and the parent  page is updated to account for the new  subdivision of key ranges.


WITH THIS INFORMATION,WRITE A COHERENT TEXT FOR MY NOTES. TRY TO KEEP AS MUCH TEXT THAT I ATTACHED AS POSSIBLE. ADD SECTIONS AND SUBSECTIONS IF NEEDED. TREE STRUCTURES (B-Trees, Log-Structured Merge (LSM) Trees)
SPARSE TABLE