Suricata

Analysis

A PR was created replacing the current red black trees with rank balanced trees: https://github.com/OISF/suricata/pull/10327

Red Black Trees vs Rank Balanced Trees

I found a few days back that BSD had replaced their Red Black Tree implementation with Rank Balanced Trees some time back (ref: https://github.com/freebsd/freebsd-src/commit/504ba65c8c9f7a3bf25303ff539f6432b9c76848). This was done because Rank Balanced Trees are much better balanced compared to the Red Black Trees (which by definition are only approximately balanced). However, given that some extra processing goes into balancing a Rank Balanced Tree, they're better suited for use cases where retrieval is of utmost importance. So, if Insertion/Deletion operations were more prominently done to the tree compared to retrieval, a Red Black Tree is still an ideal choice.

Testing results on Suricata codebase

When Victor ran the Rank Balanced Tree approach against a worst case scenario PCAP, it was found that Rank Balanced Trees were slightly more expensive than the Red Black Trees showing that insertion/deletion are more important to us than retrieval hence making Red Black Tree the ideal choice for the cases so far covered in the codebase.

Conclusion

Red Black Trees are the ideal choice for Suricata, we do not need to use Rank Balanced Trees at least for the current covered use cases.