B+樹在數據庫中的應用
{
為什麼使用B+樹?言簡意赅，就是因為：
1.文件很大，不可能全部存儲在內存中，故要存儲到磁盤上
2.索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數(為什麼使用B-/+Tree，還跟磁盤存取原理有關。)
3.局部性原理與磁盤預讀，預讀的長度一般為頁(page)的整倍數，(在許多操作系統中，頁得大小通常為4k)
4.數據庫系統巧妙利用了磁盤預讀原理，將一個節點的大小設為等於一個頁，這樣每個節點只需要一次I/O就可以完全載入，(由於節點中有兩個數組，所以地址連續)。而紅黑樹這種結構，h明顯要深的多。由於邏輯上很近的節點(父子)物理上可能很遠，無法利用局部性
InnoDB 與 MyISAM 結構上的區別
1.InnoDB的主鍵索引 ，MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在InnoDB中，表數據文件本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄。這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主索引，所以必須有主鍵，如果沒有顯示定義，自動為生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形2.InnoDB的輔助索引(Secondary Index， 也就是非主鍵索引)也會包含主鍵列，比如名字建立索引，內部節點 會包含名字，葉子節點會包含該名字對應的主鍵的值，如果主鍵定義的比較大，其他索引也將很大3.MyISAM引擎使用B+Tree作為索引結構，索引文件葉節點的data域存放的是數據記錄的地址，指向數據文件中對應的值，每個節點只有該索引列的值
4.MyISAM主索引和輔助索引(Secondary key)在結構上沒有任何區別，只是主索引要求key是唯一的，輔助索引可以重復，
(由於MyISAM輔助索引在葉子節點上存儲的是數據記錄的地址，和主鍵索引一樣，所以相對於B+的InnoDB可通過輔助索引
快速找到所有的數據，而不需要再遍歷一邊主鍵索引，所以適用於OLAP)
InnoDB索引和MyISAM索引的區別：
一是主索引的區別，InnoDB的數據文件本身就是索引文件。而MyISAM的索引和數據是分開的。
二是輔助索引的區別：InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區別。
}
1. 索引在數據庫中的作用
在數據庫系統的使用過程當中，數據的查詢是使用最頻繁的一種數據操作。
最基本的查詢算法當然是順序查找(linear search)，遍歷表然後逐行匹配行值是否等於待查找的關鍵字，其時間復雜度為O(n)。但時間復雜度為O(n)的算法規模小的表，負載輕的數據庫，也能有好的性能。 但是數據增大的時候，時間復雜度為O(n)的算法顯然是糟糕的，性能就很快下降了。
好在計算機科學的發展提供了很多更優秀的查找算法，例如二分查找(binary search)、二叉樹查找(binary tree search)等。如果稍微分析一下會發現，每種查找算法都只能應用於特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用於二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構(例如，理論上不可能同時將兩列都按順序進行組織)，所以，在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。
索引是對數據庫表 中一個或多個列的值進行排序的結構。與在表 中搜索所有的行相比，索引用指針 指向存儲在表中指定列的數據值，然後根據指定的次序排列這些指針，有助於更快地獲取信息。通常情 況下 ，只有當經常查詢索引列中的數據時 ，才需要在表上創建索引。索引將占用磁盤空間，並且影響數 據更新的速度。但是在多數情況下 ，索引所帶來的數據檢索速度優勢大大超過它的不足之處。
2. B+樹在數據庫索引中的應用
目前大部分數據庫系統及文件系統都采用B-Tree或其變種B+Tree作為索引結構
1)在數據庫索引的應用
在數據庫索引的應用中，B+樹按照下列方式進行組織 ：
① 葉結點的組織方式 。B+樹的查找鍵 是數據文件的主鍵 ，且索引是稠密的。也就是說 ，葉結點 中為數據文件的第一個記錄設有一個鍵、指針對 ，該數據文件可以按主鍵排序，也可以不按主鍵排序 ;數據文件按主鍵排序，且 B +樹是稀疏索引 ， 在葉結點中為數據文件的每一個塊設有一個鍵、指針對 ;數據文件不按鍵屬性排序 ，且該屬性是 B +樹 的查找鍵 ， 葉結點中為數據文件裡出現的每個屬性K設有一個鍵 、 指針對 ， 其中指針執行排序鍵值為 K的 記錄中的第一個。
② 非葉結點 的組織方式。B+樹 中的非葉結點形成 了葉結點上的一個多級稀疏索引。 每個非葉結點中至少有ceil( m/2 ) 個指針 ， 至多有 m 個指針 。
2)B+樹索引的插入和刪除
①在向數據庫中插入新的數據時，同時也需要向數據庫索引中插入相應的索引鍵值 ，則需要向 B+樹 中插入新的鍵值。即上面我們提到的B-樹插入算法。
②當從數據庫中刪除數據時，同時也需要從數據庫索引中刪除相應的索引鍵值 ，則需要從 B+樹 中刪 除該鍵值 。即B-樹刪除算法
