開發(fā)崗位 | 小紅書是給的真多，我想沖了...

Redis 是由 C 語言實(shí)現(xiàn)的，在 Redis 6.0 版本之前采用的正是「單 Reactor 單進(jìn)程」的方案，因?yàn)?Redis 業(yè)務(wù)處理主要是在內(nèi)存中完成，操作的速度是很快的，性能瓶頸不在 CPU 上，所以 Redis 對于命令的處理是單進(jìn)程的方案。

到 Redis 6.0 之后，就將網(wǎng)絡(luò)IO的處理改成多線程的方式了，目的是為了這是因?yàn)殡S著網(wǎng)絡(luò)硬件的性能提升，Redis 的性能瓶頸有時(shí)會(huì)出現(xiàn)在網(wǎng)絡(luò) I/O 的處理上。

所以為了提高網(wǎng)絡(luò) I/O 的并行度，Redis 6.0 對于網(wǎng)絡(luò) I/O 采用多線程來處理。但是對于命令的執(zhí)行，Redis 仍然使用單線程來處理，所以大家不要誤解 Redis 有多線程同時(shí)執(zhí)行命令。

Redis為什么快

官方使用基準(zhǔn)測試的結(jié)果是，單線程的 Redis 吞吐量可以達(dá)到 10W/每秒，如下圖所示：

之所以 Redis 采用單線程（網(wǎng)絡(luò) I/O 和執(zhí)行命令）那么快，有如下幾個(gè)原因：

• • Redis 的大部分操作

  都在內(nèi)存中完成

• • ，并且采用了高效的數(shù)據(jù)結(jié)構(gòu)，因此 Redis 瓶頸可能是機(jī)器的內(nèi)存或者網(wǎng)絡(luò)帶寬，而并非 CPU，既然 CPU 不是瓶頸，那么自然就采用單線程的解決方案了；Redis 采用單線程模型可以

  避免了多線程之間的競爭

• • ，省去了多線程切換帶來的時(shí)間和性能上的開銷，而且也不會(huì)導(dǎo)致死鎖問題。Redis 采用了

  I/O 多路復(fù)用機(jī)制

處理大量的客戶端 Socket 請求，IO 多路復(fù)用機(jī)制是指一個(gè)線程處理多個(gè) IO 流，就是我們經(jīng)常聽到的 select/epoll 機(jī)制。簡單來說，在 Redis 只運(yùn)行單線程的情況下，該機(jī)制允許內(nèi)核中，同時(shí)存在多個(gè)監(jiān)聽 Socket 和已連接 Socket。內(nèi)核會(huì)一直監(jiān)聽這些 Socket 上的連接請求或數(shù)據(jù)請求。一旦有請求到達(dá)，就會(huì)交給 Redis 線程處理，這就實(shí)現(xiàn)了一個(gè) Redis 線程處理多個(gè) IO 流的效果。

Redis哪些地方使用了多線程

edis 單線程指的是「接收客戶端請求->解析請求 ->進(jìn)行數(shù)據(jù)讀寫等操作->發(fā)送數(shù)據(jù)給客戶端」這個(gè)過程是由一個(gè)線程（主線程）來完成的，這也是我們常說 Redis 是單線程的原因。
但是，Redis 程序并不是單線程的，Redis 在啟動(dòng)的時(shí)候，是會(huì)啟動(dòng)后臺(tái)線程（BIO）的：

Redis 在 2.6 版本，會(huì)啟動(dòng) 2 個(gè)后臺(tái)線程，分別處理關(guān)閉文件、AOF 刷盤這兩個(gè)任務(wù)；

Redis 在 4.0 版本之后，新增了一個(gè)新的后臺(tái)線程，用來異步釋放 Redis 內(nèi)存，也就是 lazyfree 線程。例如執(zhí)行 unlink key / flushdb async / flushall async 等命令，會(huì)把這些刪除操作交給后臺(tái)線程來執(zhí)行，好處是不會(huì)導(dǎo)致 Redis 主線程卡頓。因此，當(dāng)我們要?jiǎng)h除一個(gè)大 key 的時(shí)候，不要使用 del 命令刪除，因?yàn)?del 是在主線程處理的，這樣會(huì)導(dǎo)致 Redis 主線程卡頓，因此我們應(yīng)該使用 unlink 命令來異步刪除大key。

之所以 Redis 為「關(guān)閉文件、AOF 刷盤、釋放內(nèi)存」這些任務(wù)創(chuàng)建單獨(dú)的線程來處理，是因?yàn)檫@些任務(wù)的操作都是很耗時(shí)的，如果把這些任務(wù)都放在主線程來處理，那么 Redis 主線程就很容易發(fā)生阻塞，這樣就無法處理后續(xù)的請求了。

后臺(tái)線程相當(dāng)于一個(gè)消費(fèi)者，生產(chǎn)者把耗時(shí)任務(wù)丟到任務(wù)隊(duì)列中，消費(fèi)者（BIO）不停輪詢這個(gè)隊(duì)列，拿出任務(wù)就去執(zhí)行對應(yīng)的方法即可。

雖然 Redis 的主要工作（網(wǎng)絡(luò) I/O 和執(zhí)行命令）一直是單線程模型，但是在 Redis 6.0 版本之后，也采用了多個(gè) I/O 線程來處理網(wǎng)絡(luò)請求，這是因?yàn)殡S著網(wǎng)絡(luò)硬件的性能提升，Redis 的性能瓶頸有時(shí)會(huì)出現(xiàn)在網(wǎng)絡(luò) I/O 的處理上。

所以為了提高網(wǎng)絡(luò) I/O 的并行度，Redis 6.0 對于網(wǎng)絡(luò) I/O 采用多線程來處理。但是對于命令的執(zhí)行，Redis 仍然使用單線程來處理，所以大家不要誤解 Redis 有多線程同時(shí)執(zhí)行命令。

Redis 官方表示，Redis 6.0 版本引入的多線程 I/O 特性對性能提升至少是一倍以上。

Redis 6.0 版本支持的 I/O 多線程特性，默認(rèn)情況下 I/O 多線程只針對發(fā)送響應(yīng)數(shù)據(jù)（write client socket），并不會(huì)以多線程的方式處理讀請求（read client socket）。要想開啟多線程處理客戶端讀請求，就需要把 Redis.conf 配置文件中的 io-threads-do-reads 配置項(xiàng)設(shè)為 yes。

//讀請求也使用io多線程
io-threads-do-reads?yes

同時(shí)， Redis.conf 配置文件中提供了 IO 多線程個(gè)數(shù)的配置項(xiàng)。

//?io-threads?N，表示啟用?N-1?個(gè)?I/O?多線程（主線程也算一個(gè)?I/O?線程）
io-threads?4

關(guān)于線程數(shù)的設(shè)置，官方的建議是如果為 4 核的 CPU，建議線程數(shù)設(shè)置為 2 或 3，如果為 8 核 CPU 建議線程數(shù)設(shè)置為 6，線程數(shù)一定要小于機(jī)器核數(shù)，線程數(shù)并不是越大越好。
因此， Redis 6.0 版本之后，Redis 在啟動(dòng)的時(shí)候，默認(rèn)情況下會(huì)額外創(chuàng)建 6 個(gè)線程（_這里的線程數(shù)不包括主線程_）：

Redis-server ： Redis的主線程，主要負(fù)責(zé)執(zhí)行命令；bio_close_file、bio_aof_fsync、bio_lazy_free：三個(gè)后臺(tái)線程，分別異步處理關(guān)閉文件任務(wù)、AOF刷盤任務(wù)、釋放內(nèi)存任務(wù)；io_thd_1、io_thd_2、io_thd_3：三個(gè) I/O 線程，io-threads 默認(rèn)是 4 ，所以會(huì)啟動(dòng) 3（4-1）個(gè) I/O 多線程，用來分擔(dān) Redis 網(wǎng)絡(luò) I/O 的壓力。

講一下Redis底層的數(shù)據(jù)結(jié)構(gòu)

Redis 提供了豐富的數(shù)據(jù)類型，常見的有五種數(shù)據(jù)類型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

隨著 Redis 版本的更新，后面又支持了四種數(shù)據(jù)類型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。Redis 五種數(shù)據(jù)類型的應(yīng)用場景：

String 類型的應(yīng)用場景：緩存對象、常規(guī)計(jì)數(shù)、分布式鎖、共享 session 信息等。List 類型的應(yīng)用場景：消息隊(duì)列（但是有兩個(gè)問題：1. 生產(chǎn)者需要自行實(shí)現(xiàn)全局唯一 ID；2. 不能以消費(fèi)組形式消費(fèi)數(shù)據(jù)）等。Hash 類型：緩存對象、購物車等。Set 類型：聚合計(jì)算（并集、交集、差集）場景，比如點(diǎn)贊、共同關(guān)注、抽獎(jiǎng)活動(dòng)等。Zset 類型：排序場景，比如排行榜、電話和姓名排序等。

Redis 后續(xù)版本又支持四種數(shù)據(jù)類型，它們的應(yīng)用場景如下：

BitMap（2.2 版新增）：二值狀態(tài)統(tǒng)計(jì)的場景，比如簽到、判斷用戶登陸狀態(tài)、連續(xù)簽到用戶總數(shù)等；HyperLogLog（2.8 版新增）：海量數(shù)據(jù)基數(shù)統(tǒng)計(jì)的場景，比如百萬級網(wǎng)頁 UV 計(jì)數(shù)等；GEO（3.2 版新增）：存儲(chǔ)地理位置信息的場景，比如滴滴叫車；Stream（5.0 版新增）：消息隊(duì)列，相比于基于 List 類型實(shí)現(xiàn)的消息隊(duì)列，有這兩個(gè)特有的特性：自動(dòng)生成全局唯一消息ID，支持以消費(fèi)組形式消費(fèi)數(shù)據(jù)。

跳表和壓縮列表是怎么實(shí)現(xiàn)的？

跳表

Redis 只有 Zset 對象的底層實(shí)現(xiàn)用到了跳表，跳表的優(yōu)勢是能支持平均 O(logN) 復(fù)雜度的節(jié)點(diǎn)查找。

鏈表在查找元素的時(shí)候，因?yàn)樾枰鹨徊檎遥圆樵冃史浅５?，時(shí)間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過來的，實(shí)現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。

那跳表長什么樣呢？我這里舉個(gè)例子，下圖展示了一個(gè)層級為 3 的跳表。

圖中頭節(jié)點(diǎn)有 L0~L2 三個(gè)頭指針，分別指向了不同層級的節(jié)點(diǎn)，然后每個(gè)層級的節(jié)點(diǎn)都通過指針連接起來：

L0 層級共有 5 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn)1、2、3、4、5；L1 層級共有 3 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn) 2、3、5；L2 層級只有 1 個(gè)節(jié)點(diǎn)，也就是節(jié)點(diǎn) 3 。

如果我們要在鏈表中查找節(jié)點(diǎn) 4 這個(gè)元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點(diǎn) 4，因?yàn)榭梢栽陬^節(jié)點(diǎn)直接從 L2 層級跳到節(jié)點(diǎn) 3，然后再往前遍歷找到節(jié)點(diǎn) 4。

可以看到，這個(gè)查找過程就是在多個(gè)層級上跳來跳去，最后定位到元素。當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度就是 O(logN)。

那跳表節(jié)點(diǎn)是怎么實(shí)現(xiàn)多層級的呢？這就需要看「跳表節(jié)點(diǎn)」的數(shù)據(jù)結(jié)構(gòu)了，如下：

typedef?struct?zskiplistNode?{
????//Zset?對象的元素值
????sds?ele;
????//元素權(quán)重值
????double?score;
????//后向指針
????struct?zskiplistNode?*backward;
??
????//節(jié)點(diǎn)的level數(shù)組，保存每層上的前向指針和跨度
????struct?zskiplistLevel?{
????????struct?zskiplistNode?*forward;
????????unsigned?long?span;
????}?level[];
}?zskiplistNode;

Zset 對象要同時(shí)保存「元素」和「元素的權(quán)重」，對應(yīng)到跳表節(jié)點(diǎn)結(jié)構(gòu)里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個(gè)跳表節(jié)點(diǎn)都有一個(gè)后向指針（struct zskiplistNode *backward），指向前一個(gè)節(jié)點(diǎn)，目的是為了方便從跳表的尾節(jié)點(diǎn)開始訪問節(jié)點(diǎn)，這樣倒序查找時(shí)很方便。

跳表是一個(gè)帶有層級關(guān)系的鏈表，而且每一層級可以包含多個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)通過指針連接起來，實(shí)現(xiàn)這一特性就是靠跳表節(jié)點(diǎn)結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類型的 level 數(shù)組。

level 數(shù)組中的每一個(gè)元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個(gè)跳表節(jié)點(diǎn)的指針」和「跨度」，跨度時(shí)用來記錄兩個(gè)節(jié)點(diǎn)之間的距離。

比如，下面這張圖，展示了各個(gè)節(jié)點(diǎn)的跨度。

第一眼看到跨度的時(shí)候，以為是遍歷操作有關(guān)，實(shí)際上并沒有任何關(guān)系，遍歷操作只需要用前向指針（struct zskiplistNode *forward）就可以完成了。

Redis 跳表在創(chuàng)建節(jié)點(diǎn)的時(shí)候，隨機(jī)生成每個(gè)節(jié)點(diǎn)的層數(shù)，并沒有嚴(yán)格維持相鄰兩層的節(jié)點(diǎn)數(shù)量比例為 2 : 1 的情況。

具體的做法是，跳表在創(chuàng)建節(jié)點(diǎn)時(shí)候，會(huì)生成范圍為[0-1]的一個(gè)隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個(gè)隨機(jī)數(shù)，直到隨機(jī)數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點(diǎn)的層數(shù)。

這樣的做法，相當(dāng)于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。

雖然我前面講解跳表的時(shí)候，圖中的跳表的「頭節(jié)點(diǎn)」都是 3 層高，但是其實(shí)如果層高最大限制是 64，那么在創(chuàng)建跳表「頭節(jié)點(diǎn)」的時(shí)候，就會(huì)直接創(chuàng)建 64 層高的頭節(jié)點(diǎn)。

壓縮列表

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的，它是由連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，有點(diǎn)類似于數(shù)組。

壓縮列表在表頭有三個(gè)字段：

zlbytes，記錄整個(gè)壓縮列表占用對內(nèi)存字節(jié)數(shù)；_

zltail，記錄壓縮列表「尾部」節(jié)點(diǎn)距離起始地址由多少字節(jié)，也就是列表尾的偏移量；_

zllen，記錄壓縮列表包含的節(jié)點(diǎn)數(shù)量；_

zlend，標(biāo)記壓縮列表的結(jié)束點(diǎn)，固定值 0xFF（十進(jìn)制255）。

在壓縮列表中，如果我們要查找定位第一個(gè)元素和最后一個(gè)元素，可以通過表頭三個(gè)字段（zllen）的長度直接定位，復(fù)雜度是 O(1)。而查找其他元素時(shí)，就沒有這么高效了，只能逐個(gè)查找，此時(shí)的復(fù)雜度就是 O(N) 了，因此壓縮列表不適合保存過多的元素。

另外，壓縮列表節(jié)點(diǎn)（entry）的構(gòu)成如下：

壓縮列表節(jié)點(diǎn)包含三部分內(nèi)容：

prevlen，記錄了「前一個(gè)節(jié)點(diǎn)」的長度，目的是為了實(shí)現(xiàn)從后向前遍歷；_

encoding，記錄了當(dāng)前節(jié)點(diǎn)實(shí)際數(shù)據(jù)的「類型和長度」，類型主要有兩種：字符串和整數(shù)。_

data，記錄了當(dāng)前節(jié)點(diǎn)的實(shí)際數(shù)據(jù)，類型和長度都由 encoding 決定；

當(dāng)我們往壓縮列表中插入數(shù)據(jù)時(shí)，壓縮列表就會(huì)根據(jù)數(shù)據(jù)類型是字符串還是整數(shù)，以及數(shù)據(jù)的大小，會(huì)使用不同空間大小的 prevlen 和 encoding 這兩個(gè)元素里保存的信息，這種根據(jù)數(shù)據(jù)大小和類型進(jìn)行不同的空間大小分配的設(shè)計(jì)思想，正是 Redis 為了節(jié)省內(nèi)存而采用的。

壓縮列表的缺點(diǎn)是會(huì)發(fā)生連鎖更新的問題，因此連鎖更新一旦發(fā)生，就會(huì)導(dǎo)致壓縮列表占用的內(nèi)存空間要多次重新分配，這就會(huì)直接影響到壓縮列表的訪問性能。

所以說，雖然壓縮列表緊湊型的內(nèi)存布局能節(jié)省內(nèi)存開銷，但是如果保存的元素?cái)?shù)量增加了，或是元素變大了，會(huì)導(dǎo)致內(nèi)存重新分配，最糟糕的是會(huì)有「連鎖更新」的問題。

因此，壓縮列表只會(huì)用于保存的節(jié)點(diǎn)數(shù)量不多的場景，只要節(jié)點(diǎn)數(shù)量足夠小，即使發(fā)生連鎖更新，也是能接受的。

雖說如此，Redis 針對壓縮列表在設(shè)計(jì)上的不足，在后來的版本中，新增設(shè)計(jì)了兩種數(shù)據(jù)結(jié)構(gòu)：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。這兩種數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)目標(biāo)，就是盡可能地保持壓縮列表節(jié)省內(nèi)存的優(yōu)勢，同時(shí)解決壓縮列表的「連鎖更新」的問題。

如何保證緩存的一致性？

緩存是通過犧牲強(qiáng)一致性來提高性能的。這是由CAP理論決定的。緩存系統(tǒng)適用的場景就是非強(qiáng)一致性的場景，它屬于CAP中的AP。所以，如果需要數(shù)據(jù)庫和緩存數(shù)據(jù)保持強(qiáng)一致，就不適合使用緩存。

所以使用緩存提升性能，就是會(huì)有數(shù)據(jù)更新的延遲。這需要我們在設(shè)計(jì)時(shí)結(jié)合業(yè)務(wù)仔細(xì)思考是否適合用緩存。然后緩存一定要設(shè)置過期時(shí)間，這個(gè)時(shí)間太短、或者太長都不好：

太短的話請求可能會(huì)比較多的落到數(shù)據(jù)庫上，這也意味著失去了緩存的優(yōu)勢。太長的話緩存中的臟數(shù)據(jù)會(huì)使系統(tǒng)長時(shí)間處于一個(gè)延遲的狀態(tài)，而且系統(tǒng)中長時(shí)間沒有人訪問的數(shù)據(jù)一直存在內(nèi)存中不過期，浪費(fèi)內(nèi)存。

但是，通過一些方案優(yōu)化處理，是可以最終一致性的。

針對刪除緩存異常的情況，可以使用 2 個(gè)方案避免：

刪除緩存重試策略（消息隊(duì)列）訂閱 binlog，再刪除緩存（Canal+消息隊(duì)列）

消息隊(duì)列方案

我們可以引入消息隊(duì)列，將第二個(gè)操作（刪除緩存）要操作的數(shù)據(jù)加入到消息隊(duì)列，由消費(fèi)者來操作數(shù)據(jù)。

• • 如果應(yīng)用

  刪除緩存失敗

• • ，可以從消息隊(duì)列中重新讀取數(shù)據(jù)，然后再次刪除緩存，這個(gè)就是

  重試機(jī)制

• • 。當(dāng)然，如果重試超過的一定次數(shù)，還是沒有成功，我們就需要向業(yè)務(wù)層發(fā)送報(bào)錯(cuò)信息了。如果

  刪除緩存成功

，就要把數(shù)據(jù)從消息隊(duì)列中移除，避免重復(fù)操作，否則就繼續(xù)重試。

舉個(gè)例子，來說明重試機(jī)制的過程。

重試刪除緩存機(jī)制還可以，就是會(huì)造成好多業(yè)務(wù)代碼入侵。

訂閱 MySQL binlog，再操作緩存

「先更新數(shù)據(jù)庫，再刪緩存」的策略的第一步是更新數(shù)據(jù)庫，那么更新數(shù)據(jù)庫成功，就會(huì)產(chǎn)生一條變更日志，記錄在 binlog 里。

于是我們就可以通過訂閱 binlog 日志，拿到具體要操作的數(shù)據(jù)，然后再執(zhí)行緩存刪除，阿里巴巴開源的 Canal 中間件就是基于這個(gè)實(shí)現(xiàn)的。

Canal 模擬 MySQL 主從復(fù)制的交互協(xié)議，把自己偽裝成一個(gè) MySQL 的從節(jié)點(diǎn)，向 MySQL 主節(jié)點(diǎn)發(fā)送 dump 請求，MySQL 收到請求后，就會(huì)開始推送 Binlog 給 Canal，Canal 解析 Binlog 字節(jié)流之后，轉(zhuǎn)換為便于讀取的結(jié)構(gòu)化數(shù)據(jù)，供下游程序訂閱使用。

下圖是 Canal 的工作原理：

將binlog日志采集發(fā)送到MQ隊(duì)列里面，然后編寫一個(gè)簡單的緩存刪除消息者訂閱binlog日志，根據(jù)更新log刪除緩存，并且通過ACK機(jī)制確認(rèn)處理這條更新log，保證數(shù)據(jù)緩存一致性

Java

ConcurrentHashMap為什么是線程安全的？

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是數(shù)組加鏈表的形式實(shí)現(xiàn)的，而數(shù)組又分為：大數(shù)組 Segment 和小數(shù)組 HashEntry。

Segment 是一種可重入鎖（ReentrantLock），在 ConcurrentHashMap 里扮演鎖的角色；HashEntry 則用于存儲(chǔ)鍵值對數(shù)據(jù)。一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組，一個(gè) Segment 里包含一個(gè) HashEntry 數(shù)組，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素。

JDK 1.7 ConcurrentHashMap 分段鎖技術(shù)將數(shù)據(jù)分成一段一段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問其中一個(gè)段數(shù)據(jù)的時(shí)候，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 雖然是線程安全的，但因?yàn)樗牡讓訉?shí)現(xiàn)是數(shù)組 + 鏈表的形式，所以在數(shù)據(jù)比較多的情況下訪問是很慢的，因?yàn)橐闅v整個(gè)鏈表，而 JDK 1.8 則使用了數(shù)組 + 鏈表/紅黑樹的方式優(yōu)化了 ConcurrentHashMap 的實(shí)現(xiàn)，具體實(shí)現(xiàn)結(jié)構(gòu)如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通過 volatile + CAS 或者 synchronized 來實(shí)現(xiàn)的線程安全的。添加元素時(shí)首先會(huì)判斷容器是否為空：

如果為空則使用 ?volatile ?加 ?CAS ?來初始化如果容器不為空，則根據(jù)存儲(chǔ)的元素計(jì)算該位置是否為空。
• 如果根據(jù)存儲(chǔ)的元素計(jì)算結(jié)果為空，則利用 ?CAS ?設(shè)置該節(jié)點(diǎn)；如果根據(jù)存儲(chǔ)的元素計(jì)算結(jié)果不為空，則使用 synchronized ?，然后，遍歷桶中的數(shù)據(jù)，并替換或新增節(jié)點(diǎn)到桶中，最后再判斷是否需要轉(zhuǎn)為紅黑樹，這樣就能保證并發(fā)訪問時(shí)的線程安全了。

如果把上面的執(zhí)行用一句話歸納的話，就相當(dāng)于是ConcurrentHashMap通過對頭結(jié)點(diǎn)加鎖來保證線程安全的，鎖的粒度相比 Segment 來說更小了，發(fā)生沖突和加鎖的頻率降低了，并發(fā)操作的性能就提高了。而且 JDK 1.8 使用的是紅黑樹優(yōu)化了之前的固定鏈表，那么當(dāng)數(shù)據(jù)量比較大的時(shí)候，查詢性能也得到了很大的提升，從之前的 O(n) 優(yōu)化到了 O(logn) 的時(shí)間復(fù)雜度。

OS

講一下銀行家算法

系統(tǒng)發(fā)生死鎖是很正常的，我們需要主動(dòng)去預(yù)防死鎖，即進(jìn)行有序的資源分配，使用銀行家算法。銀行家算法是最有代表性的避免死鎖的算法。
為什么叫銀行家算法呢？就是這個(gè)算法的邏輯很像銀行放貸的邏輯，也就是盡可能避免壞賬的出現(xiàn)。
銀行家算法的業(yè)務(wù)邏輯如下。

不負(fù)荷執(zhí)行：一個(gè)進(jìn)程的最大需求量不超過系統(tǒng)擁有的總資源數(shù)，才會(huì)被接納執(zhí)行。

可分期：一個(gè)進(jìn)程可以分期請求資源，但總請求書不可超過最大需求量。

推遲分配：當(dāng)系統(tǒng)現(xiàn)有資源數(shù)小于進(jìn)程需求時(shí)，對進(jìn)程的需求可以延遲分配，但總讓進(jìn)程在有限時(shí)間內(nèi)獲取資源。

聽起來有點(diǎn)繞，我們還是舉個(gè)例子來說明。

假如系統(tǒng)中有三類互斥資源 R1、R2、R3，可用資源數(shù)分別是 9、8、5，在指定時(shí)刻有 P1、P2、P3、P4 和 P5 這五個(gè)進(jìn)程，這些進(jìn)程的對三類互斥資源的最大需求量和已分配資源數(shù)如下表所示，那么系統(tǒng)如何先后運(yùn)行這五個(gè)進(jìn)程，不會(huì)發(fā)生死鎖問題？

第一步：分析

首先分析首次需求的資源，系統(tǒng)剩余可用資源數(shù)分別是 2、1、0，各進(jìn)程需要的資源數(shù)如下表所示。

資源 R1 的剩余可用資源數(shù) = 9 - 1 - 2 - 2 - 1 - 1 = 2。
資源 R2 的剩余可用資源數(shù) = 8 - 2 - 1 - 1 - 2 - 1 = 1。
資源 R3 的剩余可用資源數(shù) = 5 - 1 - 1 - 0 - 0 - 3 = 0。

根據(jù)銀行家算法不負(fù)荷原則【一個(gè)進(jìn)程的最大需求量不超過系統(tǒng)擁有的總資源數(shù)，才會(huì)被接納執(zhí)行】，優(yōu)先給進(jìn)程 P2 執(zhí)行，因?yàn)槭Ｓ嗟?0 1 0 資源夠讓 P2 執(zhí)行。

第二步：執(zhí)行 P2

P2 執(zhí)行之后，釋放了剛剛放入的 2 1 0 資源，而且可以釋放已分配的 2 1 1 資源，所以此時(shí)的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 2 - 0 +（2 + 0） = 4。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 1 - 1 + （1 + 1） = 2。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 0 - 0 +（0 + 1） = 1。

執(zhí)行完成 P2 后，操作系統(tǒng)剩余可用資源數(shù)為 4 2 1。

第三步：執(zhí)行 P4

此時(shí)操作系統(tǒng)剩余可用資源數(shù)為 4 2 1，只能執(zhí)行進(jìn)程 P4，因?yàn)槠渌M(jìn)程資源不夠。

P4 執(zhí)行之后，釋放了剛剛放入的 0 0 1 資源，而且可以釋放已分配的 1 2 1 資源，所以此時(shí)的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 4 - 0 +（1 + 0） = 5。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 2 - 0 + （2 + 0） = 4。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 1 - 1 +（1 + 1） = 2。

執(zhí)行完成 P4 后，操作系統(tǒng)剩余可用資源數(shù)為 5 4 2。

第四步：執(zhí)行 P5

此時(shí)操作系統(tǒng)剩余可用資源數(shù)為 5 4 2，只能執(zhí)行進(jìn)程 P5，因?yàn)槠渌M(jìn)程資源不夠。

P5 執(zhí)行之后，釋放了剛剛放入的 2 3 1 資源，而且可以釋放已分配的 1 1 3 資源，所以此時(shí)的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 5 - 2 +（1 + 2） = 6。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 4 - 3 + （1 + 3） = 5。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 2 - 1 +（3 + 1） = 5。

執(zhí)行完成 P5 后，操作系統(tǒng)剩余可用資源數(shù)為 6 5 5。

第五步：執(zhí)行 P1 或者 P3

此時(shí)操作系統(tǒng)剩余可用資源數(shù)為 6 5 5，可以執(zhí)行 P1 或 P3。

所以安全執(zhí)行順序?yàn)?p2 => p4 => p5 => p1 => p3 或 p2 => p4 => p5 => p3 => p1。

在這里插入圖片描述或在這里插入圖片描述

銀行家算法總結(jié)

銀行家算法的核心思想，就是在分配給進(jìn)程資源前，首先判斷這個(gè)進(jìn)程的安全性，也就是預(yù)執(zhí)行，判斷分配后是否產(chǎn)生死鎖現(xiàn)象。如果系統(tǒng)當(dāng)前資源能滿足其執(zhí)行，則嘗試分配，如果不滿足則讓該進(jìn)程等待。通過不斷檢查剩余可用資源是否滿足某個(gè)進(jìn)程的最大需求，如果可以則加入安全序列，并把該進(jìn)程當(dāng)前持有的資源回收；不斷重復(fù)這個(gè)過程，看最后能否實(shí)現(xiàn)讓所有進(jìn)程都加入安全序列。安全序列一定不會(huì)發(fā)生死鎖，但沒有死鎖不一定是安全序列。

講一下頁表

分頁是把整個(gè)虛擬和物理內(nèi)存空間切成一段段固定尺寸的大小。這樣一個(gè)連續(xù)并且尺寸固定的內(nèi)存空間，我們叫頁（_Page_）。在 Linux 下，每一頁的大小為 4KB。
虛擬地址與物理地址之間通過頁表來映射，如下圖：

頁表是存儲(chǔ)在內(nèi)存里的，內(nèi)存管理單元 （_MMU_）就做將虛擬內(nèi)存地址轉(zhuǎn)換成物理地址的工作。

而當(dāng)進(jìn)程訪問的虛擬地址在頁表中查不到時(shí)，系統(tǒng)會(huì)產(chǎn)生一個(gè)缺頁異常，進(jìn)入系統(tǒng)內(nèi)核空間分配物理內(nèi)存、更新進(jìn)程頁表，最后再返回用戶空間，恢復(fù)進(jìn)程的運(yùn)行。

內(nèi)存分頁由于內(nèi)存空間都是預(yù)先劃分好的，也就不會(huì)像內(nèi)存分段一樣，在段與段之間會(huì)產(chǎn)生間隙非常小的內(nèi)存，這正是分段會(huì)產(chǎn)生外部內(nèi)存碎片的原因。而采用了分頁，頁與頁之間是緊密排列的，所以不會(huì)有外部碎片。

但是，因?yàn)閮?nèi)存分頁機(jī)制分配內(nèi)存的最小單位是一頁，即使程序不足一頁大小，我們最少只能分配一個(gè)頁，所以頁內(nèi)會(huì)出現(xiàn)內(nèi)存浪費(fèi)，所以針對內(nèi)存分頁機(jī)制會(huì)有內(nèi)部內(nèi)存碎片的現(xiàn)象。

在分頁機(jī)制下，虛擬地址分為兩部分，頁號和頁內(nèi)偏移。頁號作為頁表的索引，頁表包含物理頁每頁所在物理內(nèi)存的基地址，這個(gè)基地址與頁內(nèi)偏移的組合就形成了物理內(nèi)存地址，見下圖。

總結(jié)一下，對于一個(gè)內(nèi)存地址轉(zhuǎn)換，其實(shí)就是這樣三個(gè)步驟：

把虛擬內(nèi)存地址，切分成頁號和偏移量；根據(jù)頁號，從頁表里面，查詢對應(yīng)的物理頁號；直接拿物理頁號，加上前面的偏移量，就得到了物理內(nèi)存地址。

下面舉個(gè)例子，虛擬內(nèi)存中的頁通過頁表映射為了物理內(nèi)存中的頁，如下圖：

講下為什么進(jìn)程之下還要設(shè)計(jì)線程，線程之間怎么通信的

為什么要設(shè)計(jì)線程

我們舉個(gè)例子，假設(shè)你要編寫一個(gè)視頻播放器軟件，那么該軟件功能的核心模塊有三個(gè)：

從視頻文件當(dāng)中讀取數(shù)據(jù)；對讀取的數(shù)據(jù)進(jìn)行解壓縮；把解壓縮后的視頻數(shù)據(jù)播放出來；

對于單進(jìn)程的實(shí)現(xiàn)方式，我想大家都會(huì)是以下這個(gè)方式：對于單進(jìn)程的這種方式，存在以下問題：

播放出來的畫面和聲音會(huì)不連貫，因?yàn)楫?dāng) CPU 能力不夠強(qiáng)的時(shí)候，Read 的時(shí)候可能進(jìn)程就等在這了，這樣就會(huì)導(dǎo)致等半天才進(jìn)行數(shù)據(jù)解壓和播放；各個(gè)函數(shù)之間不是并發(fā)執(zhí)行，影響資源的使用效率；

那改進(jìn)成多進(jìn)程的方式：

對于多進(jìn)程的這種方式，依然會(huì)存在問題：

進(jìn)程之間如何通信，共享數(shù)據(jù)？維護(hù)進(jìn)程的系統(tǒng)開銷較大，如創(chuàng)建進(jìn)程時(shí)，分配資源、建立 PCB；終止進(jìn)程時(shí)，回收資源、撤銷 PCB；進(jìn)程切換時(shí)，保存當(dāng)前進(jìn)程的狀態(tài)信息；

那到底如何解決呢？需要有一種新的實(shí)體，滿足以下特性：

實(shí)體之間可以并發(fā)運(yùn)行；實(shí)體之間共享相同的地址空間；

這個(gè)新的實(shí)體，就是**線程( Thread )**，線程之間可以并發(fā)運(yùn)行且共享相同的地址空間。

線程間的通信方式

Linux系統(tǒng)提供了五種用于線程通信的方式：互斥鎖、讀寫鎖、條件變量、自旋鎖和信號量。

互斥鎖（Mutex）：互斥量(mutex)從本質(zhì)上說是一把鎖，在訪問共享資源前對互斥量進(jìn)行加鎖，在訪問完成后釋放互斥量上的鎖。對互斥量進(jìn)行加鎖以后，任何其他試圖再次對互斥鎖加鎖的線程將會(huì)阻塞直到當(dāng)前線程釋放該互斥鎖。如果釋放互斥鎖時(shí)有多個(gè)線程阻塞，所有在該互斥鎖上的阻塞線程都會(huì)變成可運(yùn)行狀態(tài)，第一個(gè)變?yōu)檫\(yùn)行狀態(tài)的線程可以對互斥鎖加鎖，其他線程將會(huì)看到互斥鎖依然被鎖住，只能回去再次等待它重新變?yōu)榭捎谩?/p>

條件變量（Condition Variables）：條件變量(cond)是在多線程程序中用來實(shí)現(xiàn)"等待--》喚醒"邏輯常用的方法。條件變量利用線程間共享的全局變量進(jìn)行同步的一種機(jī)制，主要包括兩個(gè)動(dòng)作：一個(gè)線程等待"條件變量的條件成立"而掛起；另一個(gè)線程使“條件成立”。為了防止競爭，條件變量的使用總是和一個(gè)互斥鎖結(jié)合在一起。線程在改變條件狀態(tài)前必須首先鎖住互斥量，函數(shù)pthread_cond_wait把自己放到等待條件的線程列表上，然后對互斥鎖解鎖(這兩個(gè)操作是原子操作)。在函數(shù)返回時(shí)，互斥量再次被鎖住。

自旋鎖（Spinlock）：自旋鎖通過 CPU 提供的 CAS 函數(shù)（_Compare And Swap_），在「用戶態(tài)」完成加鎖和解鎖操作，不會(huì)主動(dòng)產(chǎn)生線程上下文切換，所以相比互斥鎖來說，會(huì)快一些，開銷也小一些。一般加鎖的過程，包含兩個(gè)步驟：第一步，查看鎖的狀態(tài)，如果鎖是空閑的，則執(zhí)行第二步；第二步，將鎖設(shè)置為當(dāng)前線程持有；使用自旋鎖的時(shí)候，當(dāng)發(fā)生多線程競爭鎖的情況，加鎖失敗的線程會(huì)「忙等待」，直到它拿到鎖。CAS 函數(shù)就把這兩個(gè)步驟合并成一條硬件級指令，形成

原子指令，這樣就保證了這兩個(gè)步驟是不可分割的，要么一次性執(zhí)行完兩個(gè)步驟，要么兩個(gè)步驟都不執(zhí)行。這里的「忙等待」可以用 while 循環(huán)等待實(shí)現(xiàn)，不過最好是使用 CPU 提供的 PAUSE 指令來實(shí)現(xiàn)「忙等待」，因?yàn)榭梢詼p少循環(huán)等待時(shí)的耗電量。

信號量（Semaphores）：信號量可以是命名的（有名信號量）或無名的（僅限于當(dāng)前進(jìn)程內(nèi)的線程），用于控制對資源的訪問次數(shù)。通常

信號量表示資源的數(shù)量，對應(yīng)的變量是一個(gè)整型（sem）變量。另外，還有兩個(gè)原子操作的系統(tǒng)調(diào)用函數(shù)來控制信號量的

• ，分別是：_P 操作_：將 sem 減 1，相減后，如果 sem < 0，則進(jìn)程/線程進(jìn)入阻塞等待，否則繼續(xù)，表明 P 操作可能會(huì)阻塞；_V 操作_：將 sem 加 1，相加后，如果 sem <= 0，喚醒一個(gè)等待中的進(jìn)程/線程，表明 V 操作不會(huì)阻塞；

讀寫鎖（Read-Write Locks）：讀寫鎖從字面意思我們也可以知道，它由「讀鎖」和「寫鎖」兩部分構(gòu)成，如果只讀取共享資源用「讀鎖」加鎖，如果要修改共享資源則用「寫鎖」加鎖。所以，讀寫鎖適用于能明確區(qū)分讀操作和寫操作的場景。

• • 讀寫鎖的工作原理是：當(dāng)「寫鎖」沒有被線程持有時(shí)，多個(gè)線程能夠并發(fā)地持有讀鎖，這大大提高了共享資源的訪問效率，因?yàn)椤缸x鎖」是用于讀取共享資源的場景，所以多個(gè)線程同時(shí)持有讀鎖也不會(huì)破壞共享資源的數(shù)據(jù)。但是，一旦「寫鎖」被線程持有后，讀線程的獲取讀鎖的操作會(huì)被阻塞，而且其他寫線程的獲取寫鎖的操作也會(huì)被阻塞。所以說，寫鎖是獨(dú)占鎖，因?yàn)槿魏螘r(shí)刻只能有一個(gè)線程持有寫鎖，類似互斥鎖和自旋鎖，而讀鎖是共享鎖，因?yàn)樽x鎖可以被多個(gè)線程同時(shí)持有。知道了讀寫鎖的工作原理后，我們可以發(fā)現(xiàn)，

  讀寫鎖在讀多寫少的場景，能發(fā)揮出優(yōu)勢。

MySQL

講一講mysql的引擎吧，你有什么了解？

MySQL中常用的存儲(chǔ)引擎分別是：MyISAM存儲(chǔ)引擎、innoDB存儲(chǔ)引擎，他們的區(qū)別在于：

事務(wù)：InnoDB 支持事務(wù)，MyISAM 不支持事務(wù)，這是 MySQL 將默認(rèn)存儲(chǔ)引擎從 MyISAM 變成 InnoDB 的重要原因之一。索引結(jié)構(gòu)：InnoDB 是聚簇索引，MyISAM 是非聚簇索引。聚簇索引的文件存放在主鍵索引的葉子節(jié)點(diǎn)上，因此 InnoDB 必須要有主鍵，通過主鍵索引效率很高。但是輔助索引需要兩次查詢，先查詢到主鍵，然后再通過主鍵查詢到數(shù)據(jù)。因此，主鍵不應(yīng)該過大，因?yàn)橹麈I太大，其他索引也都會(huì)很大。而 MyISAM 是非聚簇索引，數(shù)據(jù)文件是分離的，索引保存的是數(shù)據(jù)文件的指針。主鍵索引和輔助索引是獨(dú)立的。鎖粒度：InnoDB 最小的鎖粒度是行鎖，MyISAM 最小的鎖粒度是表鎖。一個(gè)更新語句會(huì)鎖住整張表，導(dǎo)致其他查詢和更新都會(huì)被阻塞，因此并發(fā)訪問受限。count 的效率：InnoDB 不保存表的具體行數(shù)，執(zhí)行 select count(*) from table 時(shí)需要全表掃描。而MyISAM 用一個(gè)變量保存了整個(gè)表的行數(shù)，執(zhí)行上述語句時(shí)只需要讀出該變量即可，速度很快。

講一下mysql里的鎖？

在 MySQL 里，根據(jù)加鎖的范圍，可以分為全局鎖、表級鎖和行鎖三類。

全局鎖：通過flush tables with read lock 語句會(huì)將整個(gè)數(shù)據(jù)庫就處于只讀狀態(tài)了，這時(shí)其他線程執(zhí)行以下操作，增刪改或者表結(jié)構(gòu)修改都會(huì)阻塞。全局鎖主要應(yīng)用于做

全庫邏輯備份，這樣在備份數(shù)據(jù)庫期間，不會(huì)因?yàn)閿?shù)據(jù)或表結(jié)構(gòu)的更新，而出現(xiàn)備份文件的數(shù)據(jù)與預(yù)期的不一樣。

表級鎖：MySQL 里面表級別的鎖有這幾種：

• • 表鎖：通過lock tables 語句可以對表加表鎖，表鎖除了會(huì)限制別的線程的讀寫外，也會(huì)限制本線程接下來的讀寫操作。元數(shù)據(jù)鎖：當(dāng)我們對數(shù)據(jù)庫表進(jìn)行操作時(shí)，會(huì)自動(dòng)給這個(gè)表加上 MDL，對一張表進(jìn)行 CRUD 操作時(shí)，加的是

MDL 讀鎖；對一張表做結(jié)構(gòu)變更操作的時(shí)候，加的是MDL 寫鎖

• • ；MDL 是為了保證當(dāng)用戶對表執(zhí)行 CRUD 操作時(shí)，防止其他線程對這個(gè)表結(jié)構(gòu)做了變更。意向鎖：當(dāng)執(zhí)行插入、更新、刪除操作，需要先對表加上「意向獨(dú)占鎖」，然后對該記錄加獨(dú)占鎖。

意向鎖的目的是為了快速判斷表里是否有記錄被加鎖。

行級鎖：InnoDB 引擎是支持行級鎖的，而 MyISAM 引擎并不支持行級鎖。

• 記錄鎖，鎖住的是一條記錄。而且記錄鎖是有 S 鎖和 X 鎖之分的，滿足讀寫互斥，寫寫互斥間隙鎖，只存在于可重復(fù)讀隔離級別，目的是為了解決可重復(fù)讀隔離級別下幻讀的現(xiàn)象。Next-Key Lock 稱為臨鍵鎖，是 Record Lock + Gap Lock 的組合，鎖定一個(gè)范圍，并且鎖定記錄本身。

MySQL主從復(fù)制了解嗎

MySQL 的主從復(fù)制依賴于 binlog ，也就是記錄 MySQL 上的所有變化并以二進(jìn)制形式保存在磁盤上。復(fù)制的過程就是將 binlog 中的數(shù)據(jù)從主庫傳輸?shù)綇膸焐稀?br /> 這個(gè)過程一般是異步的，也就是主庫上執(zhí)行事務(wù)操作的線程不會(huì)等待復(fù)制 binlog 的線程同步完成。

MySQL 集群的主從復(fù)制過程梳理成 3 個(gè)階段：

寫入 Binlog：主庫寫 binlog 日志，提交事務(wù)，并更新本地存儲(chǔ)數(shù)據(jù)。

同步 Binlog：把 binlog 復(fù)制到所有從庫上，每個(gè)從庫把 binlog 寫到暫存日志中。

回放 Binlog：回放 binlog，并更新存儲(chǔ)引擎中的數(shù)據(jù)。

具體詳細(xì)過程如下：

MySQL 主庫在收到客戶端提交事務(wù)的請求之后，會(huì)先寫入 binlog，再提交事務(wù)，更新存儲(chǔ)引擎中的數(shù)據(jù)，事務(wù)提交完成后，返回給客戶端“操作成功”的響應(yīng)。從庫會(huì)創(chuàng)建一個(gè)專門的 I/O 線程，連接主庫的 log dump 線程，來接收主庫的 binlog 日志，再把 binlog 信息寫入 relay log 的中繼日志里，再返回給主庫“復(fù)制成功”的響應(yīng)。從庫會(huì)創(chuàng)建一個(gè)用于回放 binlog 的線程，去讀 relay log 中繼日志，然后回放 binlog 更新存儲(chǔ)引擎中的數(shù)據(jù)，最終實(shí)現(xiàn)主從的數(shù)據(jù)一致性。

在完成主從復(fù)制之后，你就可以在寫數(shù)據(jù)時(shí)只寫主庫，在讀數(shù)據(jù)時(shí)只讀從庫，這樣即使寫請求會(huì)鎖表或者鎖記錄，也不會(huì)影響讀請求的執(zhí)行。

主從延遲都有什么處理方法？

強(qiáng)制走主庫方案：對于大事務(wù)或資源密集型操作，直接在主庫上執(zhí)行，避免從庫的額外延遲。

B+樹的特點(diǎn)是什么？

B+樹是一種自平衡的多路查找樹，所有葉節(jié)點(diǎn)都位于同一層，保證了樹的平衡，使得搜索、插入和刪除操作的時(shí)間復(fù)雜度為對數(shù)級別的。非葉節(jié)點(diǎn)僅包含索引信息，不存儲(chǔ)具體的數(shù)據(jù)記錄，它們只用來引導(dǎo)搜索到正確的葉節(jié)點(diǎn)。非葉節(jié)點(diǎn)的子樹指針與關(guān)鍵字?jǐn)?shù)量相同，每個(gè)子樹指針指向一個(gè)子樹，子樹中的所有鍵值都在某個(gè)區(qū)間內(nèi)。所有數(shù)據(jù)記錄都存儲(chǔ)在葉節(jié)點(diǎn)中，且葉節(jié)點(diǎn)中的數(shù)據(jù)是按關(guān)鍵字排序的。葉節(jié)點(diǎn)包含實(shí)際的數(shù)據(jù)和關(guān)鍵字，它們是數(shù)據(jù)存儲(chǔ)和檢索的實(shí)體單元。葉節(jié)點(diǎn)之間通過指針相互鏈接，形成一個(gè)鏈表，便于范圍查詢和順序遍歷。