haproxy - Haproxy 中的弹性二叉搜索树

Question

我只是看了一下HAproxy的源码来了解它是如何实现的，我看到了一个有趣的数据结构，叫做Elastic Binary Search tree .它似乎与二叉搜索树非常相似。但我想知道为负载均衡器选择这种数据结构有什么不同以及背后的原因。

Answer 1

您可以在此处找到实现细节:http://1wt.eu/articles/ebtree/

简而言之，常规二叉树和 ebtree 的主要区别在于，在常规二叉树中，您需要分配中间节点来附加叶子，而在某些环境中，必须在中间分配一个节点才能插入叶子是不方便。使用 ebtrees，每个结构既是节点又是叶子，并且由于一些指针操作，它们可以单独使用。这种可能性伴随着上面文章中描述的许多有趣的属性，例如 O(1) 删除、对重复键的支持等......

与 rbtrees 相比，在 haproxy 中使用 ebtrees 的好处是 O(1) 删除，这使得对于不断添加/删除条目的调度程序来说，ebtrees 比 rbtrees 快得多。与 BST(这是导致 ebtrees 的原始设计)相比，插入非常快(没有 malloc)并且 remoal 不需要 free()。

正在开发新版本以节省空间。它将具有与 rbtrees 相同的复杂性，但内存使用量更小。这对于存储大量经常查找但很少删除的数据很有用(例如:haproxy 的棒表、缓存等)。