分布式计算原理本文仅仅是私人MEMO，仅仅起到私人记录大纲之(8)

?????? PriorityQueue 保证最高或者最低优先级的的元素总是在队列头部，但是 LinkedHashMap 维持的顺序是元素插入的顺序。当遍历一个 PriorityQueue 时，没有任何顺序保证，但是 LinkedHashMap 课保证遍历顺序是元素插入的顺序。

?????? LinkedHashMap底层存在一个双向链表，用这个双向链表记录Entry的存储顺序，对LinkedHashMap遍历实际上是对这个双向链表。

?????? PriorityQueue底层是最小堆 但是是用数组实现的

B树

?????? 二叉搜索树 所有非叶子节点之多拥有两个儿子 所有节点存储一个关键字 非叶子结点左指针指向小于关键字的子树 右指针指向大于其关键字的子树

B-树

?????? 多路搜索树

B-树的特性：

???????????? 1.关键字集合分布在整颗树中；

???????????? 2.任何一个关键字出现且只出现在一个结点中；

???????????? 3.搜索有可能在非叶子结点结束；

???????????? 4.其搜索性能等价于在关键字全集内做一次二分查找；

???????????? 5.自动层次控制；

???????????? B-树限制了除根节点以外的非叶子结点 至少含有M/2个儿子 确保了结点的至少利用率

B+树

?????? B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

???????????? 1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

???????????? 2.不可能在非叶子结点命中；

???????????? 3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

???????????? 4.更适合文件索引系统；

???????????? 原因：相对于B树，（1）B+树空间利用率更高，因为B+树的内部节点只是作为索引使用，而不像B-树那样每个节点都需要存储硬盘指针。

??（2）增删文件（节点）时，效率更高，因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。

B*树

???? 是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

小结：

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；

???? 所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

?????? 它更适合文件索引系统；

???????????? 原因：相对于B树，（1）B+树空间利用率更高，因为B+树的内部节点只是作为索引使用，而不像B-树那样每个节点都需要存储硬盘指针。

?????????????????????????? （2）增删文件（节点）时，效率更高，因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

Comparable和Comparator的作用和区别：

?????? 都是用来自定义class的比较大小的

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-87102-8.html