On Wed, Feb 22, 2012 at 2:37 PM, Juraj Vitko <[email protected]> wrote:
> The problem with tree (ordered) maps is that they usually take more > space and are slower than hash maps. So that's why I proposed a > separate Map and OrderedMap. > > Plus, often times one needs to store a sequential structure, e.g. to > implement a Queue, or Stack, etc. It's possible to implement a list on > top of ordered map though, but one has to generate unique keys. > > Doubly linked list takes up too much memory, and Array is terrible for > insertion, but C++ STL's Deque solves this by providing a list > consisting of multiple Array chunks. > Yes, deques are great, but you'll probably also want fast indexed access. Then you'll find you may need (sublinear) concat, slice, splice, reverse, etc. Finger trees are a general purpose data structure that let you compose collections that do all of things quite easily. Oh, and it has this other advantage of being persistent (read: immutable), so you also get some other neat advantages (everything's a snapshot -- it can't mutate on you even if you dip into the event loop). Using structural sharing it's able to offer all of the above handy operations while returning you what appears to be a completely new list, and very quickly. And this immutability has another neat benefit: you could pass these immutable objects around between "worker" threads within the same process freely. It's a shame node-core had to punt on threaded workers but that doesn't mean this can't be done from a module. It's possible libuv may never be threadsafe, but no bother -- being able to safely share certain types of objects between threads means the worker environment could be limited to pure compute. Thus, you could theoretically build a kickass fibanocci benchmark, and all would finally be right with the world. > HOWEVER - the paper that I noticed today (http://goo.gl/71aFc) - seems > to offer a cool ordered Map structure that also happens to be faster > than any Hash Map currently in use. It also does this in SMP way, so > multiple Node instances in local Node Cluster could even use such DB > together. Let's hope they don't slap a patent on it. > This looks really cool. Although it's important to remember that there are a number of ways to accomplish this. I haven't looked closely at this paper yet but I bet clojure's shallow tries have similar qualities and ought to port to javascript pretty cleanly. But yeah, there's a ton of interesting data structure goodness out there the javascript community needs to start stealing :) > Re: the CouchDB - I'd imagine this is already a higher level > functionality - something that people should be able to implement and > evolve on top of the basic primitive operations, > like .put(k,v), .get(k), .range(k1, k2). > Much of what couch does is commodity, yes, but there is something particularly unique about their b+tree implementation. It will cache calculated reduction values in its interior nodes so they don't have to be run over and over. This can be really handy but it's not without its problems. Interestingly, fingertrees let you do the same thing in a more flexible yet correct manner (composable "meters" that measure and persist any data you want about children..."monoids" FTW). This feature is what allows you to do all the things I mentioned above. > I'm looking for a good paper or book pondering complex schema design > on key/value stores, but haven't had much time to do a proper googling > for it yet. > If you find anything I'd be really interested in hearing about it. -- Job Board: http://jobs.nodejs.org/ Posting guidelines: https://github.com/joyent/node/wiki/Mailing-List-Posting-Guidelines You received this message because you are subscribed to the Google Groups "nodejs" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/nodejs?hl=en?hl=en
