fbpx
Uncategorized

什麼是 B+ Tree

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

什麼是 B-tree (Balance tree)

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