Re:The Cat-And-Mouse Story of Implementing Anti-Spam for Mai...
by Robin_Message on Wednesday August 31, 2016 @12:50PM
(#12399683)
The spam bit sounds cool but the nosql db sounds odd. E.G. That tree implementation with batched rebalancing sounds downright scary, and I thought avl was considered the worst kind of balanced tree due to excessive overhead (an int per node to red-black's bit) .
[ Parent
| on HN ]
Re:The Cat-And-Mouse Story of Implementing Anti-Spam for Mai...
by bigbes on Wednesday August 31, 2016 @06:57PM
(#12402094)
> Our investigation revealed that in case of frequent insertions and deletions Tarantool initiated a complex process of tree rebalancing (all our indexes were of TREE type).
It's all about 1.5. New version (1.6) uses brand new bps-tree, not sg/avl-tree. It behaves better on all workloads.
AVLTree was "temporary" hack. Our implementation works better, for their needs. BTW - AVL is not bad, but it's hard to implement a good one (believe me :) ).
Re:The Cat-And-Mouse Story of Implementing Anti-Spam for Mai...
by Robin_Message on Thursday September 01, 2016 @05:30AM
(#12403938)
Nice. Yeah, AVL is definitely okay but it makes me happy to hear something better is in there :)
What sort of tree is this new bps-tree?
Re:The Cat-And-Mouse Story of Implementing Anti-Spam for Mai...
by bigbes on Thursday September 01, 2016 @05:33PM
(#12409074)
bps-tree means B+-tree: unique combination of B+ and B tree. You can read wiki or "The Ubiquitous B-Tree" whitepaper https://wwwold.cs.umd.edu/class/fall2002/cmsc818s/Readings/b... .
You may read code of it here: https://github.com/tarantool/tarantool/blob/1.6/src/lib/sala... . It's very thoroughly commented.