briarpig: thorn: demos: blob

demos are explained here; a menu at top column right indexes actual topic demos. Here we demo blob.

problem

In the middle 90's Wil started using a specialized btree format to represent blobs in storage systems — where a blob is basically hard to tell apart from a file embedded in a database — in imitation of tree formats described by Exodus at the University of Wisconsin (cf Storage Management for Objects in Exodus).

Given any block-oriented media for allocating space for use as nodes in tree structures (for example: pages in files using pseudo virtual memory) you can build a "file system" representing blob "files" as btrees in a manner called Exodus-style btrees in IronDoc literature. This page calls them blob btrees.

Designs and code shown on this page present a way to encode scaling byte sequences as blobs, much like files, using a tree to index leaf nodes of content. Blob btrees index using a simple scheme: inner tree nodes just count bytes of leaf content. So seeking any offset can simply skip bytes to reach a desired point. Seeks, inserts, and deletes are all logarithmic (O(logN) means "log time") at all offsets in a blob file; blob edits have the same order of performance as appending to a Unix file. So for example, deleting the first kilobyte of a 100MB blob is just as fast as truncating a kilobyte at the end — just another efficient btree edit. It's unnecessary to touch bytes downstream from a blob btree edit.

A submenu for demos appears below, letting you go to the page on a topic written as a demo (as the demos page defines it).

menu

thorn: todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob « Þ, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype