我只是看看HAproxy的来源,了解它是如何实现的,我看到一个有趣的数据结构叫做弹性二进制搜索树.它似乎对二叉搜索树非常熟悉.但我想知道为负载均衡器选择这种数据结构的不同之处和原因是什么.
您可以在此处找到实施细节:http://1wt.eu/articles/ebtree/
简而言之,常规二叉树和ebtree之间的主要区别在于,在常规二叉树中,您需要分配中间节点来附加叶子,并且在某些环境中,必须在中间分配一个节点才能插入叶子,不方便.对于ebtrees,每个结构都是一个节点和一个叶子,并且由于一些指针操作,它们都可以单独使用.这种可能性伴随着上面文章中描述的一些有趣的属性,如O(1)删除,支持重复键等...
与rbtrees相比,在haproxy中使用ebtree的好处是O(1)删除,这使得ebtrees比不断添加/删除条目的调度程序的rbtree快得多.与BST(这是导致ebtrees的原始设计)相比,插入速度非常快(没有malloc),并且remoal不需要free().
正在开发新版本以节省空间.它将具有与rbtrees相同的复杂性,但内存使用量较小.这对于存储大量数据非常有用,这些数据经常被查找并且很少被删除(例如:haproxy的棒表,缓存......).
| 归档时间： |
|
| 查看次数： |
884 次 |
| 最近记录： |