[toc]
项目说明：
- TreeMap代码在 /TreeMap/lib/src/main/java/com/example/lib/ 文件夹下
- UseOfTreeMap：可运行的 主要测试程序，已包含测试数据，运行后可查看各类方法使用
- TreeMapUtils：包括 TreeMap 所有使用方法文字注释与解析
- NavigatorTreeMap：Navigator接口示例
- HashMapCompater：HashMap与TreeMap 性能测试用例
- README.md 为说明文档
- 测试结果.txt 包含 10万、50万、100万至1000万测试数据结果。
- TreeMap用例.txt
基于红黑树实现的可排序的数据结构。
红黑树是一种非完全平衡的二叉搜索树，同时结合了 平衡二叉树 和 二叉搜索树 的性质。
红黑树的5条特征：
-
每个结点要么是红的，要么是黑的。
-
根结点是黑的。
-
每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
-
如果一个结点是红的，那么它的俩个儿子都是黑的。
-
对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点
TreeMap继承于AbstractMap，实现了Map, Cloneable, NavigableMap, Serializable接口。
-
TreeMap 实现了Map接口，成为Map框架中的一员，可以包含着key--value形式的元素；
-
TreeMap 实现了 NavigableMap接口（继承于SortedMap），意味着拥有了更强的元素搜索能力与排序功能；
-
TreeMap 实现了Cloneable接口，实现了clone()方法，可以被克隆
-
TreeMap 实现了Java.io.Serializable接口，支持序列化操作，可通过Hessian协议进行传输；
TreeMap节点结构
底层存储结构与HashMap基本相同，使用Entry对象，存储key--value键值对。
TreeMap 构造函数
所有的操作都是通过根节点来进行。
红黑树 RBT 与平衡二叉树 AVL 对比：
查找频繁 使用AVL树。
插入和删除频繁 使用性能更好的红黑树。
分析 AVL 树比红黑树更加平衡，但AVL树在插入和删除的时候会存在大量的旋转操作，影响性能。而 **红黑树 **最多进行 三次旋转。
与HashMap、ConcurrenSkipListMap对比
| 操作类型 | 插入 | 查找（在100W数据量中） | 时间 | |||||
| 10W | 50W | 100W | 150W | 0-1W | 0-25W | 0-50W | ||
| Concurrent SkipListMap | 62 ms | 227 ms | 433 ms | 689 ms | 7 ms | 80 ms | 119 ms | O(logN) |
| HashMap | 20 ms | 57 ms | 217 ms | 303 ms | 2 ms | 13 ms | 45 ms | O(log1) |
| TreeMap | 11 ms | 64 ms | 429 ms | 584 ms | 4 ms | 34 ms | 61 ms | O(logN) |
50W以下插入 使用TreeMap
50W以上插入 使用HashMap
如有排序需求，且非多线程，低并发 使用TreeMap
如有排序需求，且为多线程，高并发 使用 ConcurrentSkipListMap，适用于大规模数据的并发访问
分析：
- 当数据量较小时，HashMap扩容会引起散列冲突，解决冲突需要多花时间代价，故在f(n)=1向上浮动；
- 随着数据量的增加，HashMap的时间花费小且稳定，在单线程的环境下比TreeMap和ConcurrentSkipListMap在插入和查找上有很大的优势。
- ConcurrentSkipListMap自带锁机制
-
红黑树
常用于存储内存中的有序数据，增删很快，内存存储不涉及 I/O 操作。已用于实现 Linux 操作系统的 CPU 调度，大多数自平衡库函数，如 C++ 的 map 和 set，Java 的 TreeSet 和 TreeMap。
-
B/B+树
更适合磁盘存储，减少了树的层级，进而减少 I/O 次数；
-
B 树和 B+ 树对比
都是 B 树，但是 B+树更适合范围查询，比如 Mysql，且查询次数很稳定，为 logn。而 B 树更适合键值对型的聚合数据库，比如 MongoDB，查询次数最优为 O(1)；
红黑树更适合内存存储，B 树更适合键值对存储，B+ 树适合范围查询；
左右子树的高度差小于等于 1。平衡二叉树有两大基础操作：左旋和右旋。
右旋操作
左旋操作
又名二叉搜索树。对于二叉树中的每个节点X，它的左子树中所有项的值都小于X中的项，它的右子树中所有项的值大于X中的项。
同样的数据，也可以有不同二叉搜索树。
由于二叉搜索树可能退化成链表，所以查找操作与该树的高度相关，如果高度为节点数 N，相应查找、插入、删除的操作退化成O(N) 级别。所以，一般说二叉搜索树效率为O(logN)，只是一个估算，具体与其形状有关。为了优化，提出了红黑树。
是一种自平衡的二叉搜索树，同时 结合了平衡二叉树和二叉搜索树 的性质。满足5条性质：
- 每个结点要么是红的，要么是黑的。
- 根结点是黑的。
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
- 如果一个结点是红的，那么它的俩个儿子都是黑的。
- 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点
这些性质使红黑树保持了 logN的高度，所以红黑树的查找、插入、删除的时间复杂度 最坏为O(logN)
又叫平衡多路查找树。B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树，与红黑树类似，但在降低磁盘I/O操作方面要更好。很多数据库系统一般使用B树或者B树的变形结构。
有 N 个关键字的 X 结点，内含 N + 1 个子结点（如 D H 2个关键字的结点，有3个子女）：
B树满足条件：
