資料庫二叉樹
❶ 資料庫索引為什麼使用B+樹
B tree： 二叉樹（Binary tree），每個節點只能存儲一個數。
B-tree： B樹（B-Tree，並不是B「減」樹，橫杠為連接符，容易被誤導）
B樹屬於多叉樹又名平衡多路查找樹。每個節點可以多個數（由磁碟大小決定）。
B+tree 和 B*tree 都是 B-tree的變種
一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁碟上。這樣的話，索引查找過程中就要產生磁碟I/O消耗，相對於內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁碟I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁碟I/O的存取次數。而B-/+/*Tree，經過改進可以有效的利用系統對磁碟的塊讀取特性，在讀取相同磁碟塊的同時，盡可能多的載入索引數據，來提高索引命中效率，從而達到減少磁碟IO的讀取次數。
不了解磁碟相關知識的可以查看 硬碟基本知識（磁頭、磁軌、扇區、柱面）
下面通過示意圖來看一下，B-tree、B+tree、B*tree
從圖中可以看出，B-tree 利用了磁碟塊的特性進行構建的樹。每個磁碟塊一個節點，每個節點包含了很關鍵字。把樹的節點關鍵字增多後樹的層級比原來的二叉樹少了，減少數據查找的次數和復雜度。
B-tree巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁（每頁為4K），這樣每個節點只需要一次I/O就可以完全載入。
B-tree 的數據可以存在任何節點中。
B+tree 是 B-tree 的變種，數據只能存儲在葉子節點。
B+tree 是 B-tree 的變種，B+tree 數據只存儲在葉子節點中。這樣在B樹的基礎上每個節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快，所有指關鍵字指針都存在葉子節點，所以每次查找的次數都相同所以查詢速度更穩定;
B*tree 每個磁碟塊中又添加了對下一個磁碟塊的引用。這樣可以在當前磁碟塊滿時，不用擴容直接存儲到下一個臨近磁碟塊中。當兩個鄰近的磁碟塊都滿時，這兩個磁碟塊各分出1/3的數據重新分配一個磁碟塊，這樣這三個磁碟塊的數據都為2/3。
在B+樹的基礎上因其初始化的容量變大，使得節點空間使用率更高，而又存有兄弟節點的指針，可以向兄弟節點轉移關鍵字的特性使得B*樹額分解次數變得更少；
❷ 深入理解(二叉樹、平衡二叉樹、B-Tree、B+Tree )的區別
二叉樹、平衡二叉樹、BTree、B+Tree的主要區別如下：
1. 二叉查找樹： 基礎結構：通過二分查找法提升數據查找速度，每個節點存儲一個鍵值和數據，每個節點最多有兩個子節點。 缺點：當樹結構不平衡時，查詢效率會顯著降低。
2. 平衡二叉樹： 特點：確保樹的高度平衡，從而保持穩定的查找效率。 節點存儲：每個節點存儲單一鍵值和數據。 子節點數量：每個節點最多有兩個子節點。 優勢：通過旋轉操作保持高度平衡，提高查找效率。
3. BTree： 節點存儲：節點能存儲多個鍵值和數據，每個節點有多於兩個的子節點。 適用場景：適合海量數據存儲，通過增加節點中鍵值的數量來減少樹的高度，從而減少磁碟I/O操作。 優點：在大量數據存取時，能顯著提高查找、插入和刪除操作的效率。
4. B+Tree： 節點結構：非葉子節點僅存儲指針，葉子節點保存所有數據和指針。 查詢穩定性：由於所有實際數據都存儲在葉子節點，且葉子節點之間通過指針相連，使得查詢更加穩定。 排序性能：葉子節點形成了一個有序的鏈表，非常適合范圍查找和排序操作。 應用場景：在MySQL的InnoDB存儲引擎中，B+Tree常用於聚集索引，以提高查詢效率。
總結： 二叉查找樹是基礎數據結構，但在不平衡時效率較低。 平衡二叉樹通過保持高度平衡來提高查找效率。 BTree通過增加節點中鍵值的數量來優化存儲效率和磁碟訪問。 B+Tree在BTree的基礎上進一步改進，提高了查詢穩定性和排序性能，特別適用於資料庫索引等場景。
❸ C語言 什麼叫完全二叉樹
完全二叉樹是一種特殊的二叉樹。
定義：如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
例：
特點：
葉子結點只可能在最大的兩層上出現,對任意結點，若其右分支下的子孫最大層次為L，則其左分支下的子孫的最大層次必為L 或 L+1。
完全二叉樹第i層至多有2^（i-1）個節點，共i層的完全二叉樹最多有2^i-1個節點。
滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點的二叉樹。