Data Structures and Algorithms

free and open source software

B-Trees are not boring, after all

GZIP Compression is an extremely popular technique of lossless compression for photos, videos, & web pages. It is used by a large number of websites.

Learn about two common techniques for resolving conflicts in your database: last-write-wins (LWW) and conflict-free replicated data types (CRDTs).

Last month finally I had an opportunity to use Bloom filters. I became fascinated with the promise of this data structure, but I quickly realized it had some drawbacks.

Learn the definition of log structured merge tree and get answers to FAQs regarding: how LSM trees work to speed write operations and store keys and data efficiently.

B-trees are used by many modern DBMSs. Learn how they work, how databases use them, and how your choice of primary key can affect index performance.

This is an introduction to data structure flattening, a special case of arena allocation that is a good fit for programming language implementations. We build a simple interpreter twice, the normal way and the flat way, and show that some fairly mechanical code changes can give you a 2.4× speedup.

In this post, we'll continue onto topic of Commutative Replicated Data Types. We already mentioned [https://www.bartoszsypytkowski.com/operation-based-crdts-registers-and-sets/#sets] how to prepare first, the most basic types of collections: sets. This time we'll go take a look at indexed sequence...

An overview of erasure coding, its trade-offs, and applications in distributed storage systems.

Map is a built-in type that acts as a key-value storage. Unlike arrays where you’re stuck with keys as increasing indices like 0, 1, 2, and so on, with maps, the key can be any comparable type.

This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes. The algorithm has high performance and can be used in production.

<p>In this post, we will explore the CIDR trie data structure and how it can help you manage IP addresses and subnets in your Rust project.</p>

A blog by and for database architects.

A comparative, extendible benchmarking suite for C and C++ hash-table libraries.

By making use of randomness, a team has created a simple algorithm for estimating large numbers of distinct objects in a stream of data.

Smudge.ai is a Chrome extension that gives you ChatGPT-powered shortcuts in your right-click menu.

I'm sick of complex blogging solutions, so markdown files in a git repo it is - francisrstokes/githublog

Our modern lives are influenced by algorithms at every step. We can trace this influence back more than 1,200 years ago – to a Muslim mathematician.

How to implement a packrat parser from scratch, one easy piece at a time.

This article presents the rich text CRDT algorithm implemented in Loro, complying with [Peritext]'s criteria for seamless rich text collaboration. Furthermore, it can be built on top of any List CRDT algorithms and turn them into rich text CRDTs.

A web log. Mostly about computer science-y stuff.

We need a fast way to query multiple potentially large sets of data on-demand at interactive speeds. Sometimes the easiest solution to a hard problem is to build the right tool for the job.