Articles on Data structures

Top deep-dives on Data structures

Persistent Data Structures - An Introduction

I'd say the difference between a persistent and normal data structure is that the presistent version always has one additional dimension; time. Does that make sense? If not, Arpit Bhayani's intro should put it into context, and if it still doesn't make sense, then I'm just a poor explainer heh. Although the article is pretty brief, it outlines some of the core concepts and approaches, while linking to other, more comprehensive resources.

The quick and practical "MSI" hash table

Chris Wellons presents the method and philosophy for his standard approach to writing hash tables in C.

Implicit In-order Forests: Zooming a billion trace events at 60fps

Tristan Hume presents the "IForestIndex data structure", a spin off of an implicit binary tree, and explains how he used it to implement a trace viewer that can "smoothly zoom a trace of 1 billion randomly generated events".

Building a BFT JSON CRDT

CRDTs are a family of data structures that are used to replicate data across multiple computers. They are designed to avoid conflicts when people write data to the same place.
Some highlights:

• CRDTs mathematically guarantee that an application can safely update their local state without needing to coordinate with all of its peers
• Traditional databases focus on a property called linearizability, which guarantees that all operations behave as if executed on a single copy of the data
• CRDTs can be made fault tolerant by solving a problem called the Byzantine Broadcast

Penny Codes

A Penny code "represents the extended connectivity environment around an individual atom within a molecular graph". In this informative article, Richard L. Apodaca presents what a Penny code is and how it can be represented/computed via data structures.

Technique: Recursive variants and boxes

Jonathan Müller demonstrates how the std::variant sum type can be adjusted to handle recursive structures.