b_tree Archives - 快樂學程式

上一篇學習 什麼是 B-Tree 這篇就來補 B+ Tree 囉 B+ Tree 特徵 每個葉子節點都帶有指向下一個節點的指針，形成有序鏈表，加速範圍查詢 只有葉子節點帶衛星數據，父節點只帶關鍵字與指針，單一節點更省空間，讓查詢 I/O 變小 所有查詢都會查到葉子節點，查詢性能穩定 B+ Tree 更加矮胖 B+ Tree 中的內部節點，只存放關鍵字與子節點的指針，不存其他的 Satellite Information，因此最大化了內部節點的分支因子，所以說以同樣大小的硬碟分頁可以容納更多的節點元素。 換句話說，以數據量相同的情況下， B+ Tree 會比…

一般像是 MySQL PostgreSQL 都是用 Btree 的方式建立索引。 注意：B-tree 不念 B減樹，而是直接念 Btree，所以如果看到 Btree vs B-tree 其實是在講同一個算法。 為什麼用 Btree 用二元樹進行查詢，最快的時間複雜度是 O(logN)，以算法邏輯上面來說，二元樹搜尋的查找速度跟比較次數都是最小的，但是要注意的事，我們還需要考量一個現實的問題就是「硬碟 I/O」。 二元樹結構： 數據庫的索引都是儲存在硬碟上，當數據量龐大時，索引的大小可能會有幾 G 甚至更多。 我們不可能在透過索引查詢時，一次把幾 G…