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 :
Post a Comment