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

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

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

如果你覺(jué)得有什么問(wèn)題可以給我提issue，覺(jué)得不錯(cuò)的話你也可以star一下。目前更新的內(nèi)容并不多，因?yàn)闉榱吮ＷC文章質(zhì)量，每一篇文章我自己都看了一遍，希望大家貢獻(xiàn)自己的力量完善。

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

Queue

Java集合類分析之Queue

Set

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

List

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

ArrayList 是一個(gè)數(shù)組隊(duì)列，相當(dāng)于動(dòng)態(tài)數(shù)組。它由數(shù)組實(shí)現(xiàn)，隨機(jī)訪問(wèn)效率高，隨機(jī)插入、隨機(jī)刪除效率低。

LinkedList 是一個(gè)雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。LinkedList隨機(jī)訪問(wèn)效率低，但隨機(jī)插入、隨機(jī)刪除效率低。

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

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

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

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

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

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

Map

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

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

Stack(棧)

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

樹

1 二叉樹

二叉樹（百度百科）

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

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

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

2 完全二叉樹

完全二叉樹（百度百科）

3 滿二叉樹

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

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

4 二叉查找樹（BST）

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

二叉查找樹的特點(diǎn)：

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

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

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

沒(méi)有鍵值相等的節(jié)點(diǎn)（no duplicate nodes）。

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

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

6 紅黑樹

紅黑樹特點(diǎn):

每個(gè)節(jié)點(diǎn)不是紅色就是黑色的；

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

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

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

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

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

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

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)缺點(diǎn)比較》](https://blog.csdn.net/bigtree_3721/article/details/73632405)

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

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

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

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

8 LSM 樹

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

B+樹最大的性能問(wèn)題是會(huì)產(chǎn)生大量的隨機(jī)IO

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

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