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

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

Java面試通關(guān)手冊（Java學(xué)習(xí)指南）github 地址：https://github.com/Snailclimb/Java_Guide

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

推薦學(xué)習(xí)視頻：浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)國家精品教程

Queue

Java集合類分析之Queue

Set

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

List

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

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

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

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

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

集合框架源碼學(xué)習(xí)之ArrayList

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

集合框架源碼學(xué)習(xí)之LinkedList

java數(shù)據(jù)結(jié)構(gòu)與算法之順序表與鏈表深入分析

Map

集合框架源碼學(xué)習(xí)之HashMap(JDK1.8)

ConcurrentHashMap實現(xiàn)原理及源碼分析

Stack(棧)

java數(shù)據(jù)結(jié)構(gòu)與算法之棧（Stack）設(shè)計與實現(xiàn)

樹

1 二叉樹

二叉樹（百度百科）

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

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

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

2 完全二叉樹

完全二叉樹（百度百科）

3 滿二叉樹

滿二叉樹（百度百科，國內(nèi)外的定義不同）

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

4 二叉查找樹（BST）

淺談算法和數(shù)據(jù)結(jié)構(gòu): 七 二叉查找樹

二叉查找樹的特點：

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

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

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

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

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

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

6 紅黑樹

紅黑樹特點:

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

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

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

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

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

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

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

7 B-，B+，B*樹

[二叉樹學(xué)習(xí)筆記之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樹）是一種平衡的多路查找(又稱排序)樹，在文件系統(tǒng)中有所應(yīng)用。主要用作文件的索引。其中的B就表示平衡(Balance)

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

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

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

8 LSM 樹

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

B+樹最大的性能問題是會產(chǎn)生大量的隨機IO

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

LSM樹由來、設(shè)計思想以及應(yīng)用到HBase的索引