摘要：是棧，它繼承于。滿二叉樹除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。沒有鍵值相等的節(jié)點。這是數據庫選用樹的最主要原因。

在我們學習Java的時候，很多人會面臨我不知道繼續(xù)學什么或者面試會問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個開源平臺來幫助一些有需要的人，通過下面的內容，你會掌握系統的Java學習以及面試的相關知識。本來是想通過Gitbook的形式來制作的，后來想了想覺得可能有點大題小做。另外，我自己一個人的力量畢竟有限，希望各位有想法的朋友可以提issue和pull。

Java面試通關手冊（Java學習指南）github 地址：https://github.com/Snailclimb/Java_Guide

如果你覺得有什么問題可以給我提issue，覺得不錯的話你也可以star一下。目前更新的內容并不多，因為為了保證文章質量，每一篇文章我自己都看了一遍，希望大家貢獻自己的力量完善。

推薦學習視頻：浙江大學數據結構國家精品教程

Queue

Java集合類分析之Queue

Set

由淺入深理解java集合(二)——集合 Set

List

Java 集合系列08之 List總結(LinkedList, ArrayList等使用場景和性能分析)

ArrayList 是一個數組隊列，相當于動態(tài)數組。它由數組實現，隨機訪問效率高，隨機插入、隨機刪除效率低。

LinkedList 是一個雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率低。

Vector 是矢量隊列，和ArrayList一樣，它也是一個動態(tài)數組，由數組實現。但是ArrayList是非線程安全的，而Vector是線程安全的。

Stack 是棧，它繼承于Vector。它的特性是：先進后出(FILO, First In Last Out)。

集合框架源碼學習之ArrayList

注意ArrayList的擴容機制(注意移位運算符的使用)以及System.arraycopy()和Arrays.copyOf()方法在ArrayList集合源碼中的使用。

集合框架源碼學習之LinkedList

java數據結構與算法之順序表與鏈表深入分析

Map

集合框架源碼學習之HashMap(JDK1.8)

ConcurrentHashMap實現原理及源碼分析

Stack(棧)

java數據結構與算法之棧（Stack）設計與實現

樹

1 二叉樹

二叉樹（百度百科）

(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區(qū)別于AVL算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

2 完全二叉樹

完全二叉樹（百度百科）

3 滿二叉樹

滿二叉樹（百度百科，國內外的定義不同）

國內教程定義：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。

4 二叉查找樹（BST）

淺談算法和數據結構: 七 二叉查找樹

二叉查找樹的特點：

若任意節(jié)點的左子樹不空，則左子樹上所有結點的 值均小于它的根結點的值；

若任意節(jié)點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

任意節(jié)點的左、右子樹也分別為二叉查找樹。

沒有鍵值相等的節(jié)點（no duplicate nodes）。

5 平衡二叉樹（Self-balancing binary search tree）

平衡二叉樹（百度百科，平衡二叉樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等）

6 紅黑樹

紅黑樹特點:

每個節(jié)點不是紅色就是黑色的；

根節(jié)點總是黑色的；

所有的葉節(jié)點都是是黑色的（紅黑樹的葉子節(jié)點都是空節(jié)點（NIL或者NULL））；

如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）；

從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數目的黑色節(jié)點（即相同的黑色高度）

  [漫畫：什么是紅黑樹？](https://juejin.im/post/5a27c6946fb9a04509096248#comment)（也介紹到了二叉查找樹）
 
  [尋找紅黑樹的操作手冊](http://dandanlove.com/2018/03/18/red-black-tree/)（文章排版以及思路真的不錯）

  [紅黑樹深入剖析及Java實現](https://zhuanlan.zhihu.com/p/24367771)（美團點評技術團隊）    

7 B-，B+，B*樹

[二叉樹學習筆記之B樹、B+樹、B*樹 ](https://yq.aliyun.com/articles/38345)

[《B-樹，B+樹，B*樹詳解》](https://blog.csdn.net/aqzwss/article/details/53074186)

[《B-樹，B+樹與B*樹的優(yōu)缺點比較》](https://blog.csdn.net/bigtree_3721/article/details/73632405)

B-樹（或B樹）是一種平衡的多路查找(又稱排序)樹，在文件系統中有所應用。主要用作文件的索引。其中的B就表示平衡(Balance)

B+ 樹的葉子節(jié)點鏈表結構相比于 B- 樹便于掃庫，和范圍檢索。

B+樹支持range-query(區(qū)間查詢)非常方便，而B樹不支持。這是數據庫選用B+樹的最主要原因。

B樹 是B+樹的變體，B樹分配新結點的概率比B+樹要低，空間使用率更高；

8 LSM 樹

[[HBase] LSM樹 VS B+樹](https://blog.csdn.net/dbanote...

B+樹最大的性能問題是會產生大量的隨機IO

為了克服B+樹的弱點，HBase引入了LSM樹的概念，即Log-Structured Merge-Trees。

LSM樹由來、設計思想以及應用到HBase的索引