国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 為什么Rust標準庫的TreeMap采用B樹實現(xiàn),而不是常用的紅黑樹?

為什么Rust標準庫的TreeMap采用B樹實現(xiàn),而不是常用的紅黑樹?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 03:07:28 1696964848

一、為什么Rust標準庫的TreeMap采用B樹實現(xiàn)

簡單來說,BST確實是理論上內(nèi)存數(shù)據(jù)結(jié)構的優(yōu)異解,但是有個前提:內(nèi)存是真的均質(zhì)隨機訪問內(nèi)存。這里給出一個定義,均質(zhì)隨機訪問內(nèi)存即主存擁有在任意上下文場景下,訪問任意地址,都有著非常相似的性能。但是很不幸,現(xiàn)在的內(nèi)存并不是這樣子的。

在計算機當中,由于cache的存在,訪問臨近位置的內(nèi)存在平均意義下會產(chǎn)生非常巨大的性能提升,而BST的特性導致臨近的元素并不是在內(nèi)存中存放在一起的,從而在實踐當中性能非常糟糕。而B-Tree在大部分場景下,可以讓一些臨近元素在內(nèi)存中存放在一起,從而在大部分情況下,實踐中得到比BST更好的性能。

B-Tree相對于B+Tree的優(yōu)劣勢:

優(yōu)勢:省內(nèi)存,不需要多做一層索引。

劣勢:Iter略慢,next() 最差會出現(xiàn)log n的復雜度,B+Tree可以穩(wěn)定O(1)。

可以區(qū)分index和數(shù)據(jù),把index做的很小,放進更快但是更小的存儲中。

首先Rust的BTreeMap是全放在內(nèi)存里的,第三條基本上就沒啥用,第二條的性能提升微乎其微,但是名列前茅條的省內(nèi)存可是實實在在的,所以B+Tree在這個使用場景下GG。

再給大家添加一個B+Tree很適合的使用場景來進一步學習下B+Tree,一個典型應用是硬盤KV數(shù)據(jù)庫,開啟數(shù)據(jù)庫的時候根據(jù)硬盤中保存的葉子結(jié)點們在內(nèi)存中構造出來B+Tree的index部分,這樣子的硬盤KV的讀寫一個key一般只需要hit一次硬盤就可以完成,當然觸發(fā)平衡時候會是多次,但是相比于純硬盤BTree的log n次硬盤操作(index大 內(nèi)存塞不下)而言,優(yōu)勢非常明顯的。

延伸閱讀:

二、TreeMap概述

TreeMap存儲K-V鍵值對,通過紅黑樹(R-B tree)實現(xiàn);

TreeMap繼承了NavigableMap接口,NavigableMap接口繼承了SortedMap接口,可支持一系列的導航定位以及導航操作的方法,當然只是提供了接口,需要TreeMap自己去實現(xiàn);

TreeMap實現(xiàn)了Cloneable接口,可被克隆,實現(xiàn)了Serializable接口,可序列化;

TreeMap因為是通過紅黑樹實現(xiàn),紅黑樹結(jié)構天然支持排序,默認情況下通過Key值的自然順序進行排序;

聲明:本站稿件版權均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內(nèi)將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT