⑴ 如何在磁碟上以文件形式存儲一棵樹
參考以下代碼： #include <stdio.h> //定義二叉樹的存儲結構 struct BTNode { char data; BTNode* lchild; BTNode* rchild; }BTNode; void Ctree(struct BTNode* t,char A[],int i) { if(t!=NULL) { A[i]=t->data; Ctree(t->lchild,A,i*2); Ctree(t->rchild,A,i*2+1); } else { A[i]=' '; } } int main(void) { //建立二叉鏈表存儲結構的二叉樹,以p1為根節點，p2,p3分別為p1的左右子樹，p4為p3的左子樹 struct BTNode p1,p2,p3,p4; struct BTNode *t=&p1; p1.data='a'; p2.data='b'; p3.data='c'; p4.data='d'; p1.lchild=&p2; p1.rchild=&p3; p2.lchild=NULL; p2.rchild=NULL; p3.lchild=&p4; p3.rchild=NULL; p4.lchild=NULL; p4.rchild=NULL; char A[20]={NULL}; //定義字元數組存儲轉換後的二叉樹存儲結構 Ctree(t,A,1); //調用上述轉換演算法 //顯示結果 printf("以下是轉換後數組的值：\n"); for(int i=1;i<20;i++) { if(A[i]!=NULL) printf("A[%d]=%c\n",i,A[i]); } return 0; }
⑵ 怎麼用fwrite把一個二叉樹存到磁碟下次用呢 我這個怎麼不行 c語言
二叉樹是一種數據結構，不是數據，頭指針HEAD只是一個內存地址，寫入磁碟有啥用，二叉樹的程序終止以後，所佔用的內存要釋放回收，二叉樹中的數據全部消失了。
如果是保留二叉樹中的數據，那很簡單了，遍歷，逐個寫入就可以了。
建議你先了解清楚程序，內存，磁碟，文件這些基本的概念。
⑶ 怎樣將建立好的哈夫曼樹保存在文件中
哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如JPEG中就應用了哈夫曼編碼。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。）
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現演算法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法，可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構： struct tree{
float weight; /*權值*/union{char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/};struct tree *right; /*樹的右結點*/};struct forest{ /*F集合，以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/};例：若字母A，B，Z，C出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，101，11，對於編碼串：1010就可翻譯為bb 或ca，因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為 1，當然你也可以反過來規定。
這種編碼方法是靜態的哈夫曼編碼，它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元 0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為 0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。靜態哈夫曼編碼方法有一些缺點：一、對於過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；二、進行哈夫曼編碼，存儲編碼信息時，若用與通訊網路，就會引起較大的延時；三、對較大的文件進行編碼時，頻繁的磁碟讀寫訪問會降低數據編碼的速度。
因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。
⑷ 以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的演算法
樹的高度：對非空二叉樹，其深度等於左子樹的最大深度加1。
Int Depth(BinTree *T){int dep1,dep2;
if(T==Null) return(0);
else{dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);}
樹的寬度：按層遍歷二叉樹，採用一個隊列q，讓根結點入隊列，最後出隊列，若有左右子樹，則左右子樹根結點入隊列，如此反復，直到隊列為空。
int Width(BinTree *T){intfront=-1,rear=-1;
/*隊列初始化*／int flag=0,count=0,p;
/* pint CountNode (BTNode *t)
//節點總數{int num;if (t == NULL)num = 0;
elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);
return (num);}void CountLeaf (BTNode *t)
//葉子節點總數{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;
// 全局變數CountLeaf (t->lch);CountLeaf (t->rch);}}。
(4)二叉樹存儲磁碟擴展閱讀
方法：
求二叉樹的高度的演算法基於對二叉樹的三種遍歷，可以用後序遍歷的演算法加上記錄現在的高度和已知的最高的葉子的高度，當找到一個比已知高度還要高的葉子，刷新最高高度。
最後遍歷下來就是樹的高度，至於後序遍歷的演算法，是一本數據結構或者演算法的書中都有介紹和參考代碼
⑸ 計算機三級的內容是什麼
計算機三級考試大綱全集
一、計算機等級考試三級資料庫技術考試大綱
基本要求
1.掌握計算機系統和計算機軟體的基本概念、計算機網路的基本知識和應用知識、信息安全的基本概念。
2.掌握數據結構與演算法的基本知識並能熟練的應用。
3.掌握並能熟練運用操作系統的基本知識。
4.掌握資料庫的基本概念，深入理解關系數據模型、關系數據理論和關系資料庫系統，掌握關系數據語言。
5.掌握資料庫設計方法，具有資料庫設計能力。了解資料庫技術發展。
6.掌握計算機操作，並具有C語言編程，開發資料庫應用（含上機調試）的能力。
考試內容
一、基礎知識
1.計算機系統的組成和應用領域。
2.計算機軟體的基礎知識。
3.計算機網路的基礎知識和應用知識。
4.信息安全的基本概念。
二、數據結構與演算法
1.數據結構、演算法的基本概念。
2.線性表的定義、存儲和運算。
3.樹形結構的定義、存儲和運算。
4.排序的基本概念和排序方法。
5.檢索的基本概念和檢索演算法。
三、操作系統
1.操作系統的基本概念、主要功能和分類。
2.進程、線程、進程間的通信的基本概念。
3.存儲管理、文件管理、設備管理的主要技術。
4.典型操作系統的應用。
四、資料庫系統的基本原理
1.資料庫的基本概念，資料庫系統的組成。
2.數據模型概念和主要的數據模型。
3.關系數據模型的基本概念，關系操作和關系代數。
4.結構化查詢語言sql。
5.事務管理、並發控制、故障恢復的基本概念。
五、資料庫設計和資料庫應用
1.關系資料庫的規范化理論。
2.資料庫設計的目標、內容和方法。
3.資料庫應用開發工具。
4.資料庫技術發展。
六、上機操作
1.掌握計算機基本操作。
2.掌握C語言程序設計基本技術、編程和調試。
3.掌握與考試內容相關的知識的上機應用。
考試方式
一、筆試：120分鍾
二、上機考試：60分鍾
二、等級考試（三級信息管理技術）考試大綱
基本要求
⒈具有計算機及其應用的基礎知識。
⒉熟悉計算機操作系統、軟體工程和資料庫的原理及其應用。
⒊具有計算機體系結構、系統組成和性能評價的基礎及應用知識。
⒋具有計算機網路和通信的基礎知識。
⒌具有計算機應用項目開發的分析、設計和組織實施的基本能力。
⒍具有計算機應用系統安全和保密性知識。
考試內容
一、計算機系統組成及工作原理
⒈計算機系統組成：
⑴計算機的發展。
⑵計算機的分類及應用。
⑶計算機硬體結構。
⑷主要部件功能。
⑸計算機軟體的功能與分類。
⑹系統軟體與應用軟體。
⒉計算機工作原理：
⑴計算機中數的表示。
⑵運算器。
⑶控制器。
⑷存儲器。
⑸輸入與輸出系統。
⒊計算機的主要性能：
⑴計算機系統性能指標。
⑵處理機指標。
⑶存儲容量能力。
⑷I/O匯流排能力。
⑸系統通信能力。
⑹聯機事務處理能力。
⑺軟體支持。
二、數據結構與演算法
⒈基本概念：
⑴數據結構的基本概念。
⑵演算法的描述與分析。
⒉線性表：
⑴線性表的邏輯結構。
⑵線性表的順序存儲結構。
⑶線性表的鏈式存儲結構。
⒊數組：
⑴數組的定義與運算。
⑵數組的順序存儲結構。
⑶矩陣的壓縮存儲。
⒋棧與隊列：
⑴棧的定義和運算。
⑵棧的存儲結構。
⑶隊列的定義和運算。
⑷鏈隊列與循環隊列。
⒌串：
⑴串及其操作。
⑵串的存儲結構。
⒍樹和二叉樹：
⑴樹的定義。
⑵二叉樹的定義及性質。
⑶二叉樹與樹的轉換。
⑷二叉樹的存儲。
⑸遍歷二叉樹與線索二叉樹。
⒎圖：
⑴圖及其存儲結構。
⑵圖的遍歷。
⑶圖的連通性。
⑷有向無環圖。
⑸最短路徑。
⑹拓撲排序。
⒏查找：
⑴線性表查找。
⑵樹形結構與查找。
⑶散列查找。
⒐排序：
⑴插入排序。
⑵交換排序。
⑶選擇排序。
⑷歸並排序。
⑸基數排序。
10.組織：
⑴順序文件。
⑵索引文件。
⑶散列文件。
三、離散數學
⒈數理邏輯：
⑴命題及其符號化。
⑵命題公式及其分類。
⑶命題邏輯等值演算。
⑷範式。
⑸命題邏輯推理理論。
⑹謂詞與量詞。
⑺謂詞公式與解釋。
⑻謂詞公式的分類。
⑼謂詞邏輯等值演算與前束範式。
(10)謂詞邏輯推理理論。
⒉集合論：
⑴集合及其表示。
⑵集合的運算。
⑶有序對與笛卡爾積。
⑷關系及其表示法。
⑸關系的運算。
⑹關系的性質。
⑺關系的閉包。
⑻復合關系與逆關系。
⑼等價關系與偏序關系。
(10)函數及其性質。
(11)反函數與復合函數。
⒊代數系統：
⑴代數運算及其性質。
⑵同態與同構。
⑶半群與群。
⑷子群與陪集。
⑸正規子群與商群。
⑹循環群與置換群。
⑺環與域。
⑻格與布爾代數。
⒋圖論：
⑴無向圖與有向圖。
⑵路、迴路與圖的連通性。
⑶圖的矩陣表示。
⑷最短路徑與關鍵路徑。
⑸二部圖。
⑹歐拉圖與哈密爾頓圖。
⑺平面圖。
⑻樹與生成樹。
⑼根樹及其應用。
四、操作系統
⒈操作系統的基本概念：
⑴操作系統的功能。
⑵操作系統的基本類型。
⑶操作系統的組成。
⑷操作系統的介面。
⒉進程管理：
⑴進程、線程與進程管理。
⑵進程式控制制。
⑶進程調度。
⑷進程通信。
⑸死鎖。
⒊作業管理：
⑴作業與作業管理。
⑵作業狀態及其轉換。
⑶作業調度。
⑷作業控制。
⒋存儲管理：
⑴存儲與存儲管理。
⑵虛擬存儲原理。
⑶頁式存儲。
⑷段式存儲。
⑸段頁式存儲。
⑹局部性原理與工作集概念。
⒌文件管理：
⑴文件與文件管理。
⑵文件的分類。
⑶文件結構與存取方式。
⑷文件目錄結構。
⑸文件存儲管理。
⑹文件存取控制。
⑺文件的使用。
⒍設備管理：
⑴設備與設備分類。
⑵輸入輸出控制方式。
⑶中斷技術。
⑷通道技術。
(5)緩沖技術.
⑹設備分配技術與SPOOLING系統。
⑺磁碟調度。
⑻設備管理。
⒎一種典型操作系統（DOS/Unix/Windows）的使用：
⑴DOS的特點與使用。
⑵UNIX的特點與使用。
⑶Windows的特點與使用。
三|計算機等級考試（三級PC技術）考試大綱
基本要求
1.具有計算機及其應用的基礎知識。
2.熟悉80X86微處理器的結構、原理及其宏匯編語言程序設計。
3.掌握個人計算機的工作原理及邏輯組成和物理結構。
4.掌握Windows操作系統的主要功能、原理、配置及其維護管理。
5.熟悉個人計算機常用的外部設備的性能、原理及結構。
考試內容
一、計算機應用的基礎知識
1.計算機技術的發展，計算機信息處理的特點，計算機分類，PC機的組成與性能評測。
2.數值信息在計算機內的表示：整數的表示和運算，實數（浮點數）的表示和運算。
3.文字信息與文本在計算機內的表示：西文字元編碼字元集（Unicode）。
4.多媒體技術基礎：數字聲音的類型，波形聲音與合成聲音，圖像、圖形的特點與區別，圖像、圖形和視頻信息在計算機內的表示
5.計算機網路的基礎知識：計算機網路的功能、分類和組成。數據通信的基本原理，網路體系結構與TCP/IP協議，網際網路與IP地址，計算機區域網初步。
二、微處理器與匯編語言程序設計
1.微處理器的一般結構：寄存器組，寄存器管理，匯流排時序，工作模式以及類型提供配置。
2.Pentium微處理器的功能與結構：內部結構及工作原理，寄存器組，工作模式及存儲器管理，中斷管理，匯流排時序。
3.80X86系列微處理器指令系統：指令格式與編碼，定址方式，指令系統。
4.80X86宏匯編語言的數據、表達式和偽指令語句。
5.80X86宏匯編語言的程序設計：順序、分支及循環程序設計，子程序設計，ROBBIOS中斷調用和DOS提供功能調用。
三、PC機組成原理與介面技術
1.PC機的邏輯組成與物理結構：主板與晶元組，超級I/O晶元，主板BIOS等。
2.系統匯流排的功能與工作原理，ISA匯流排和PCI局部匯流排。
3.主存儲器的組成與工作原理：ROM和RAM，內存條與主存儲器工作原理，Cache存儲器。
4.輸入輸出控制：I/O定址方式與I/O埠地址，程序控制I/O方式，中斷控制I/O方式。DMAI/O控制方式。
5.外設介面：串列介面，並行介面，SCSI介面和IEEE－1394。
四、Windows操作系統的功能與原理
1.操作系統的功能，類型和Windows98體系結構，Windows API與DLL的基本概念。
2.Windows的處理機管理：Windows虛擬機，Windows虛擬機管理程序，Windows的進程調度技術。
3.Windows的存儲管理：Windows的內存結構與管理，Windows的虛擬內尋。
4.Windows的文件管理：Windows的文件系統結構，磁碟的存儲結構，FAT16與FAT32。
5.Windows的設備管理：虛擬設備驅動程序，通用驅動程序與小型驅動程序，即插即用與配置管理，電源管理，列印子系統等。
6.Windows的網路通信功能：Windows的網路組件，遠程網路通信，分布式組件對象模型DCOM，Windows中的Internet組件。
7.Windows的多媒體功能：Windows對多媒體文件與設備的支持，Windows的多媒體組件，Windows的媒體播放器。
8.Windows的配置、管理與維護：安裝與啟動，注冊表，系統配置與管理，系統性能監視和優化，故障診斷。
9.PC機的安全與病毒防範：計算機安全的一般概念，PC機病毒及其防範。
五、PC機的常用外圍設備
1.輸入設備：鍵盤、滑鼠器、筆輸入設備、掃描儀、數碼相機，聲音輸入設備及MIDI輸入設備。
2.輸出設備：CRT顯示其、液晶顯示器與顯示控制卡，針式列印機、激光印字機與噴墨列印機；繪圖儀；MIDI音樂合成、3D環繞聲生成與音箱；視頻輸出設備。
3.外存儲器：軟盤存儲器；硬碟存儲器的組成、原理與性能指標，活動硬碟，磁碟陣列；磁帶存儲器；光碟存儲器的原理與分類，CD-ROM、CD-R、CD-RW、DVD光碟存儲器。
4.PC機連網設備：Modem，ISDN與PC機的接入，ADSL接入，有線電視網與Cable Modem，區域網組網設備（乙太網卡與集線器），無線接入技術。
六、上機操作
1.掌握計算機基本操作。
2.熟練掌握80X86宏匯編語言程序設計的基本技術、編程和調試。
3.掌握與考試內容相關的上機應用。
考試方式
一、筆試：120分鍾
二、上機考試：60分鍾
⑹ 計算機國四都考什麼
俺知道國三的
``
國四的你上網路一搜```
大綱上什麼沒有呢````
記得是2008版的````
⑺ 如何將數據從磁碟讀出並還原成一棵二叉樹
題目的意思就是給你中序和先序的序列，讓你構造出一個二叉樹。構造時用遞歸的方法（樓主對遞歸不熟的話很難看懂理解的）
主要思想用遞歸 對照先序序列，在中序序列中確定根
中序數組in[l1...r1 ]
先序數組pre[ l2...r2]
l1 l2 r1 r2 為數組的下標范圍
演算法代碼如下：
BTNode *CreateBT(char pre[],char in [],int l1,int l2,int r1,int r2)
{
BTNode *s;
int i;
if(l1<r1)return null;
s=(BTNode*)malloc(sizeof(BTNode));
s->lchild=s->rchild=null;
for(i=l2;i<=r2;i++)
if(in[i]==pre[l1])
break;
s->data=in[i];
s->lchild=CreateBT(pre,in,l1+1,l1+i-l2,l2,i-1);
s->rchild=CreateBT(pre,in,l1+i-l2+1,r1,i+1,r2);
return s;
}
⑻ 數據結構按邏輯結構可分為兩大類,它們分別是( ) 和( )
從數據的邏輯結構分兩大類：線性結構和非線性結構，數據的存儲方法有四種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。
樹的存儲可能是基於物理上的順序存儲方式，可以理解為一個格子一個格子連續地放，設想有7個節點的二叉樹，第一個格子放根節點，第二個格子放左子樹根節點；並且根據引用知道左葉子在後續的哪個格子里；第三個格子放右子樹根節點，依此類推。此外，樹的存儲也可能是基於物理上的鏈式存儲方式。
⑼ 如何將該鏈表中的數據以文件形式保存在磁碟上
樓上的思路是正解，你要是喜歡，我還可以教你一點旁門左道的東西。
其實也簡單，就是自定義malloc函數，使得鏈表在分配空間時在一個限定區段內（比如0000~FFFF）進行分配，即你已經知道了鏈表可能存在的最大空間，然後保存時，直接用指針：
fwrite()把整個區段寫進去，然後再記錄根地址即可；
調用時，先把整個區段讀進去，然後把根地址讀出來作為根，這樣整個鏈表一共用兩個指令就完成讀寫操作了。
不要覺得有多無賴可笑，現代操作系統：WINXP / VISTA / WIN7 / LINUX / OS X等等，其快速「休眠」功能完全就是上面的解法，就是把內存和寄存器狀態一並寫入磁碟，這個方法非常快，而且不會出錯，但是能把教你數據結構的老師氣得吐血。
有人說這樣產生的文件會很大，大怕什麼，壓縮一下不就行了？反正裡面實際上放置的是一個稀疏矩陣，壓縮後的結果可能比樓上產生的文件更小。
⑽ B+樹作為Mysql索引結構的優點
面試時候經常會被問到mysql的索引結構，B+樹相較二叉樹，紅黑樹的優勢等問題，接下來就分析下這些問題。
首先，讓我們先看一張圖：
從圖中可以看到，我們為 user 表（用戶信息表）建立了一個二叉查找樹的索引。
圖中的圓為二叉查找樹的節點，節點中存儲了鍵（key）和數據（data）。鍵對應 user 表中的 id，數據對應 user 表中的行數據。
二叉查找樹的特點就是任何節點的左子節點的鍵值都小於當前節點的鍵值，右子節點的鍵值都大於當前節點的鍵值。頂端的節點我們稱為根節點，沒有子節點的節點我們稱之為葉節點。
如果我們需要查找 id=12 的用戶信息，利用我們創建的二叉查找樹索引，查找流程如下：
利用二叉查找樹我們只需要 3 次即可找到匹配的數據。如果在表中一條條的查找的話，我們需要 6 次才能找到。
上面我們講解了利用二叉查找樹可以快速的找到數據。但是，如果上面的二叉查找樹是這樣的構造：
這個時候可以看到我們的二叉查找樹變成了一個鏈表。如果我們需要查找 id=17 的用戶信息，我們需要查找 7 次，也就相當於全表掃描了。 導致這個現象的原因其實是二叉查找樹變得不平衡了，也就是高度太高了，從而導致查找效率的不穩定。為了解決這個問題，我們需要保證二叉查找樹一直保持平衡，就需要用到平衡二叉樹了。 平衡二叉樹又稱 AVL 樹，在滿足二叉查找樹特性的基礎上，要求每個節點的左右子樹的高度差不能超過 1。
下面是平衡二叉樹和非平衡二叉樹的對比：
由平衡二叉樹的構造我們可以發現第一張圖中的二叉樹其實就是一棵平衡二叉樹。
平衡二叉樹保證了樹的構造是平衡的，當我們插入或刪除數據導致不滿足平衡二叉樹不平衡時，平衡二叉樹會進行調整樹上的節點來保持平衡。具體的調整方式這里就不介紹了。平衡二叉樹相比於二叉查找樹來說，查找效率更穩定，總體的查找速度也更快。
因為內存的易失性。一般情況下，我們都會選擇將 user 表中的數據和索引存儲在磁碟這種外圍設備中。但是和內存相比，從磁碟中讀取數據的速度會慢上百倍千倍甚至萬倍，所以，我們應當盡量減少從磁碟中讀取數據的次數。另外，從磁碟中讀取數據時，都是按照磁碟塊來讀取的，並不是一條一條的讀。如果我們能把盡量多的數據放進磁碟塊中，那一次磁碟讀取操作就會讀取更多數據，那我們查找數據的時間也會大幅度降低。如果我們用樹這種數據結構作為索引的數據結構，那我們每查找一次數據就需要從磁碟中讀取一個節點，也就是我們說的一個磁碟塊。我們都知道平衡二叉樹可是每個節點只存儲一個鍵值和數據的。那說明什麼？說明每個磁碟塊僅僅存儲一個鍵值和數據！那如果我們要存儲海量的數據呢？
可以想像到二叉樹的節點將會非常多，高度也會極其高，我們查找數據時也會進行很多次磁碟 IO，我們查找數據的效率將會極低！
為了解決平衡二叉樹的這個弊端，我們應該尋找一種單個節點可以存儲多個鍵值和數據的平衡樹。也就是我們接下來要說的 B 樹。
B 樹（Balance Tree）即為平衡樹的意思，下圖即是一棵 B 樹：
圖中的 p 節點為指向子節點的指針，二叉查找樹和平衡二叉樹其實也有，因為圖的美觀性，被省略了。
圖中的每個節點稱為頁，頁就是我們上面說的磁碟塊，在 MySQL 中數據讀取的基本單位都是頁，所以我們這里叫做頁更符合 MySQL 中索引的底層數據結構。
從上圖可以看出，B 樹相對於平衡二叉樹，每個節點存儲了更多的鍵值（key）和數據（data），並且每個節點擁有更多的子節點，子節點的個數一般稱為階，上述圖中的 B 樹為 3 階 B 樹，高度也會很低。
基於這個特性，B 樹查找數據讀取磁碟的次數將會很少，數據的查找效率也會比平衡二叉樹高很多。
假如我們要查找 id=28 的用戶信息，那麼我們在上圖 B 樹中查找的流程如下：
B+ 樹是對 B 樹的進一步優化。讓我們先來看下 B+ 樹的結構圖：
根據上圖我們來看下 B+ 樹和 B 樹有什麼不同：
通過上圖可以看到，在 InnoDB 中，我們通過數據頁之間通過雙向鏈表連接以及葉子節點中數據之間通過單向鏈表連接的方式可以找到表中所有的數據。
MyISAM 中的 B+ 樹索引實現與 InnoDB 中的略有不同。在 MyISAM 中，B+ 樹索引的葉子節點並不存儲數據，而是存儲數據的文件地址。
摘自： http://www.liuzk.com/410.html