關于b樹,b+樹的問題

aliluyaaaa · 發表于 2017-12-8 20:44

為什么b樹和b+數都支持隨機查找呢？
印象中只有數組那種時間復雜度o（1）的才叫支持隨機查找，總不能把樹也順序存儲下來吧，很是不解
求解惑，謝謝了

老鐵穿鍋 · 發表于 2017-12-13 14:26

這里的隨機是按樹形索引來找的，和連續的那個隨機有區別

aliluyaaaa · 發表于 2017-12-14 21:07

老鐵穿鍋發表于 2017-12-13 14:26
這里的隨機是按樹形索引來找的，和連續的那個隨機有區別

雖然是logn。。。但查找的時候是把非葉節點理解成一個個嵌套索引嗎。

aliluyaaaa · 發表于 2017-12-14 21:10

另外，看完堆排序之后。知道了順序存儲樹是可以的，而且幾乎沒有多余的空間復雜度，反倒還是一種比較好的存儲方式。。。學無止盡啊

老鐵穿鍋 · 發表于 2017-12-17 16:33

b樹數據放在葉子節點，每次查找都是從根找到葉子，和二叉排序樹有點像。這樣子的復雜度也不是log2n，因為和階數有關。b+是葉子是用指針連在一起的的，所以可以順序查找

		自動登錄	找回密碼
密碼			注冊

NEW最新資料推薦