在分布式系统构建中，不可避免会面临诸如小型MAP级K-V存储，客户端负载均衡算法动态实现等等需要高效查询的场景，本文以负载均衡算法为场景，进行红黑树微定制的实现。
首先，列一下设计目标：
- 一般来讲，客户端部分，红黑树实现应当在服务部分，所以线程安全是必须的，JAVA本身的TreeMap虽然是红黑树的实现，但却并不是线程安全的。
- 负载均衡采用哈希环1:N虚节点查询方式[PS1.若不清楚见后文解释]，满足节点动态大量扩容调整并且避免雪崩的要求。
数据存取、操作等主要Map操作与TreeMap兼容
所以综合这些设计目标，优选的方案就是根据JAVA的TreeMap源码来进行必要的改造以满足我们的要求。TreeMap的源码可以在OpenJdk中看到，我使用的是OpenJdk 8。目录是”jdk\src\share\classes\java\util\TreeMap.java”
eclipse中绑定rt.jar源码至jdk\src\share\classes\即可直接跳转]
浏览源码可以发现 2216 - 2405 为红黑树左右旋，插入后平衡，删除及删除后平衡操作，2048 - 2114 为内部节点实现（实现了Entry接口，并且加入了颜色属性），put、get、remove操作为基础操作可直接参看实现。类比实现采用依赖最小构造的方法，即根据需求引入最少的代码逐步构建。
针对线程安全问题，由于信息变更次数很少，绝大多数为读操作，所以采用ReentrantReadWriteLock读写锁的方式可以很好的实现安全操作。接口上，还需要暴露一个边际查找接口edge，来完成左开右闭空间的左边界与右边界寻找（一般只使用左边界）。所以总体上写操作的暴露接口为put、remove操作，读操作的暴露接口为edge，采用实现一个静态代理方法的模式完成上锁与卸锁。
具体实现可参考修改后代码（部分）rbtree
关于哈希环1:N虚节点负载均衡算法
负载均衡常用的被动算法包括(加权)轮询法、(加权)随机法、哈希法等，但是这类算法在出现单点故障以及动态扩容的时候，都会面临新节点不能有效平均其他节点的负载以及分配不均以及单点压力瞬间增大引发的雪崩问题。这时候被动方案中比较简单的方案就是哈希环虚节点映射的模式了，下面举例说明。
假设银行有4个柜台，门口有无数顾客，则虚节点的方式为每个顾客根据自己的身份证号、手机号、银行卡等唯一标识，生成一个1-100之间的数字，普通的哈希算法一般会说0-25到1号柜台，依次类推，但是突然1号柜台突然有事要请假半天，这时候由于原有算法并不能调整，所以自然变成了0-50号至2号柜台，所以服务压力就变成了2:1:1，这时候2号面临多一倍的用户不堪重负倒下了。。。0-75号又集中到了3号柜台，压力就变成了3:1，3号倒下的更快，这种现象就是雪崩了。。。那1：n虚节点的方式，是4个人分别随机领10个号，用户寻找不大于自己号的虚节点中最大的那个所对应的柜台，这样100个号就被分成了4 x N个号段，随机对应4个柜台，任意连续的两个都没有必然的次序关系。这样，任何一个柜台倒下，其他几个柜台的服务压力依旧是接近1:1:1的，同时引入新的柜台，也会得到近似1:1:1:1:1的服务配比，完美