Storage engines

The storage engine is the layer that decides how keys and values are laid out and found again. Everything above it, the SQL, the transactions, the indexes, is written against IKeyValueStore and does not know or care which implementation is underneath.

Three implementations ship. B+Tree is the default, and for most applications it is also the answer. If you have no particular reason to look further, you can stop after the next section.

Selecting one

In a connection string:

Data Source=app.witdb              // B+Tree, the default
Data Source=events;Store=lsm       // LSM-Tree, note this is a folder
Data Source=:memory:               // in-memory

Or through the builder, which is the same choice spelled differently:

var db = new WitDatabaseBuilder()
    .WithFilePath("app.witdb")
    .WithBTree()
    .WithTransactions()
    .Build();

The choice is made when the database is created and is a property of the data on disk, so it is not something you flip later on an existing database.

B+Tree

A B+Tree keeps keys in sorted order across fixed-size pages and rewrites a page in place when its contents change. Reads walk down from the root, so finding one row costs a handful of page reads whatever the size of the table. Range scans follow the leaves sideways and come out in key order, which is what makes ORDER BY on an indexed column cheap and BETWEEN cheaper still.

Values too large for a page spill into overflow pages, so a TEXT or BLOB column does not force the page size up for everything else.

The B+Tree store is even-tempered. Point lookups, range scans, updates and deletes all cost about what you would expect, and none of them degrades sharply as the table grows. The database is one file, so it can be copied, attached to a bug report, or handed to a customer.

Use it unless you have measured a reason not to.

In-memory

The same interface, backed by nothing durable. The database exists while it is open and is gone afterwards.

This is the store behind Data Source=:memory:. There is no file to create, no directory to clean up and no leftover state between test runs, and nothing about the engine above it changes: the same parser, the same planner, the same constraints. See the EF Core provider for using it as a test fixture.

It works as a cache or a scratch space inside a longer-running process, where you want SQL over data that has no business surviving a restart.

LSM-Tree

An LSM-Tree buffers writes in memory and flushes them out as immutable sorted files, which a compaction merges later. It uses a folder rather than a single file, and a read may have to consult several of those files. In theory this trades read work for cheaper writes.

In this engine there is currently no workload where choosing it pays. With the settings a connection actually gets, writes through it are far slower than through the B+Tree store, because multi-version concurrency control costs an order of magnitude more over this store than over a B+Tree, charged per row, and no batch size amortises it. Setting MVCC=false brings the two stores level with each other, which means trading away snapshot isolation to arrive at parity. Neither outcome is a reason to switch.

It ships as an example of an alternative engine. LSM-Tree is a fundamentally different data structure from a B+Tree, with a different write path, a different read path and a folder instead of a file, and it answers the same IKeyValueStore interface in the same process under the same SQL. A storage engine shaped around your own data goes in the same way; see architecture.

Work on it continues. The measurements are on the benchmarks page.

Practical differences

Where to go next

• Architecture, how a store is selected and how to write your own
• Indexing, the secondary indexes that sit above whichever store you chose
• File format, what is inside the file and how versions relate
• Benchmarks, the measurements behind everything above