Re:MySQL is bazillion times faster than MemSQL
by tintor on Tuesday June 26, 2012 @03:59PM
(#4163831)
Skip list is essentially a hierarchy of linked lists. It is very hard to make a doubly linked list work concurrently without using locks. One would have to update two pointers atomically in order to insert a new element in a doubly linked list.
[ Parent
| on HN ]
Re:MySQL is bazillion times faster than MemSQL
by Nitramp on Tuesday June 26, 2012 @05:15PM
(#4164170)
You could probably pull that off if you implement it like full text search indices in e.g. Lucene. Have every modification create a "diff" skip list that takes precedence over older skip lists, and then have a merge operation that runs asynchronously (and will either have to lock, or copy the entire data structure and switch it in atomically). That's also essentially how Bigtable's disk format works.
Re:MySQL is bazillion times faster than MemSQL
by dhruvbird on Tuesday June 26, 2012 @05:22PM
(#4164211)
Actually, there are papers about it http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.4... but I don't know much about the implementation complexity since I've never implemented one.