Sunday, December 20, 2015

[xozxcnvf] Filesystem of blocks with individual extents

Store a string as a collection of fixed sized blocks.  Each block contains two pieces metadata: where within the block the data begins and ends.  That is, the data in a block does not need to fill the entirety of a block.  The blocks are organized in (probably) a balanced tree.  This data structure supports fast insertion of substrings into and deletion out of the string, at the cost of wasted space.  There is a slow compaction operation available that removes the wasted space, called perhaps when space or locality performance is needed.

Use this data structure to implement a filesystem.  Is the ability to quickly insert into and delete from the middle of a file useful?  Currently filesystems can only quickly append to the end.

No comments :