A scalable database for persistent, binary byte trees with shaded nodes

Your job is to create a database for a persistent, binary tree structure which will hold byte values. That database will be used to store a huge library of programs created with our platform, and is expected to grow to big sizes (terabytes), so it must be scalable. You must implement a smart compression algorithm that will recognise identical nodes and eliminate them. So, instead of storing trees as strings, it will store them as a flat sequence of nodes of values (bytes) and pointers. Notice the example below: ORIGINAL TREE: (((1 (2 (1 (2 0)))) (7 (1 (2 (1 (2 0)))))) ((1 (2 (1 (2 0)))) ((1 (2 (1 (2 0)))) ((1 (2 (1 (2 0)))) (5 (1 (2 (1 (2 0))))))))) (125 bytes) COMPRESSED TREE: (2 0) (1 *0) (2 *1) (1 *2) (5 *3) (*3 *4) (*3 *5) (1 *6) (16 bytes) On the compressed tree, pointers are tagged with a * . To recover the original tree, all you have to do is to dereference the pointers. For example, starting with the node (3 5), you can expand it as follows: (*3 *5) ((1 *2) (*3 *4)) ((1 (2 *1)) ((1 *2) (5 *3))) ((1 (2 (1 *0))) ((1 (2 *1)) (5 (1 *2)))) ... and so on, until the original tree is recovered. The use of that particular strategy is mandatory. Other than that, you are free to design whatever scalability techniques and strategies you like. The final product must expose an API that will allow you to: Save a tree with a name. Example: db.save_tree("program1",[1,[[3,1],[1,2]]]) Get a tree with a specific name. Example: db.get_tree("program1") = [1,[[3,1],[1,2]]] Serialise a tree to a binary format. For example, the tree used above is serialised as follows: serialize_binary(tree) = "100010100000100001000000000001000100000000000110000100000000010100101000000000110000000001100000000100000000000110000000010110000100000000110" // (17 bytes) Pack the binary serialisation of the string into a UTF16 string. That format will be used to efficient exchange of data between the server and client via Ajax. For example: pack_utf16(serialize_binary(tree)) = "七匄嘀瀀娠傔习儀渃丬嘆" // (22 bytes) Unserialise and unpack the representations above. You are free to add other operations if it proves necessary (for example, update_node(tree,path)), but that is optional. There is no preference in how the API is exposed. The final product will be put to stress tests before acceptance. The tests specifications as well as tools to perform those will be provided, so you can execute them by himself before submitting the work. You are free to chose whatever programming language or technologies you want, including existing technologies such as other databases - as long as you get the desired results. The payment can be done via paypal, bank transfer or bitcoins (preferred). Feel free to contact me for more information. Please submit your proposal together with an official note of an approximated cost, as well as examples of previous works on the area.