Btree索引插入流程分析

?專欄內(nèi)容：

• postgresql內(nèi)核源碼分析
• 手寫數(shù)據(jù)庫toadb
• 并發(fā)編程

?開源貢獻：

• toadb開源庫

個人主頁：我的主頁
管理社區(qū)：開源數(shù)據(jù)庫
座右銘：天行健，君子以自強不息；地勢坤，君子以厚德載物.

前言

B樹索引在PostgreSQL中得到了廣泛應(yīng)用，它是一種自平衡樹數(shù)據(jù)結(jié)構(gòu)，可以維護有序數(shù)據(jù)并允許進行搜索、順序訪問、插入和刪除操作。在PostgreSQL中，可以在任何數(shù)據(jù)類型上使用B樹索引，支持排序，支持大于、小于、等于、大于或等于、小于或等于的搜索。

B樹具有一些重要的特征。首先，B樹是平衡的，每個葉子頁與根都由相同數(shù)量的內(nèi)部頁分隔開，因此搜索任何值都需要花費相同的時間。其次，B樹是多分支的，每個頁面通常包含許多（數(shù)百個）ctid，因此B樹的深度很小，對于非常大的表，實際上可以達到4-5的深度。最后，索引中的數(shù)據(jù)按非遞減順序存儲（在頁面之間和每個頁面內(nèi)部），并且同一級別的頁面通過雙向列表相互連接，因此不需要每次都返回到根，可以通過遍歷鏈表獲取一個有序的數(shù)據(jù)集。

PostgreSQL中的B樹索引是一種高效的數(shù)據(jù)結(jié)構(gòu)，可以用于加速對有序數(shù)據(jù)的搜索和訪問。通過使用B樹索引，可以大大提高數(shù)據(jù)庫的性能和響應(yīng)時間。

概述

本文主要介紹postgresql 中常用的索引類型btree的插入過程，通過本文對postgresql 索引查詢的代碼有一定了解，希望能夠幫助基于postgresql做內(nèi)核開發(fā)的同學(xué)，當(dāng)然理解也有限，正在看這部分的同學(xué)可以在評論區(qū)一起來探討。

插入流程

在進行SQL語句 insert一條數(shù)據(jù)行時，如果某一列帶有索引，那么在插入數(shù)據(jù)的同時，也需要插入一條索引項；

索引項中需要記錄數(shù)據(jù)行的tid，也就是位置信息，所以插入索引的時機，是在插入數(shù)據(jù)行成功后，使用數(shù)據(jù)行的位置信息生成一條索引項，然后進行索引項的插入流程；

索引項的插入整體流程如下：

• 生成新的索引項；
• 檢查唯一性；
• 查找合適的插入位置；
• 對待插入索引頁面檢查空閑空間是否足夠；
• 如果空間不足，則將當(dāng)前索引頁面進行分裂為左右兩半；
• 然后將新索引項加入左或右頁面；

準(zhǔn)備階段

生成一個索引項，這就是需要插入的新索引項；

先是遍歷btree樹，從root中的元組進行二分查找，找到該索引項對應(yīng)的范圍所在的下層的節(jié)點的pageno，如果層級較多，每次都是如此，最終找到葉子節(jié)點，找到要插入的葉子節(jié)點的索引數(shù)據(jù)塊；

檢查唯一性

對于主鍵的列，需要檢查索引的唯一性，避免插入兩條相同的索引；

對于主鍵肯定是需要唯一的存在，為什么要在這里做唯一性檢查，而不是在數(shù)據(jù)插入時檢查呢?

因為在插入數(shù)據(jù)時，如果檢查唯一性，還是要通過索引掃描來比對，所以直接放到索引插入階段，當(dāng)索引檢查不通過時，那么前面插入的數(shù)據(jù)也是無效的。

• 檢查時，在索引樹中先找到相同值的位置；
• 然后對比它的tid是否一樣，如果不一樣，也就是除了之前新插入數(shù)據(jù)之外還有一條相同字段的數(shù)據(jù)存在；
• 檢查相同索引項對應(yīng)的數(shù)據(jù)行的事務(wù)是否提交； 如果沒有提交，則等待該事務(wù)結(jié)束，再進行檢查；
• 如果相同索引項對應(yīng)的數(shù)據(jù)行的事務(wù)已經(jīng)提交，那么就產(chǎn)生了沖突；
• 當(dāng)有沖突時，就會報錯，abort當(dāng)前事務(wù)，也就會導(dǎo)致前面插入的數(shù)據(jù)無效；

查找合適的插入位置

在前一步已經(jīng)找到了符合的葉子節(jié)點，在 _bt_findinsertloc 中，還需要進一步查找合適的位置，主要有以下幾種情況：

• 對于非heapkeyspace的索引，相同鍵值索引項，需要插入到最右邊；此時要向右查找節(jié)點；
• 對于多個索引頁面都有相同highkey，也就是重復(fù)值，那么這些頁面都適合插入新值，找一個空間足夠的即可；
• 還有一種情況是，對于數(shù)據(jù)多版本需要跨頁時，要新增索引項，此時索引項的值是不變的，只是對應(yīng)的tid發(fā)生了變化；對于這種情況，可以先檢查刪除的dead索項，避免索引的分裂；

在上面向右查找的情況，postgresql做了一些優(yōu)化，綜合了向右找的代價，和提前分裂的代價，有概率提前分裂；

對于新插入的索引項，不能大于空閑空間的三分之一;

檢查空閑空間

在 _bt_insertonpg 調(diào)用中，實現(xiàn)了剩余空間檢查，頁面分裂，索引項的真正插入；

當(dāng)前查找到索引頁空間小于當(dāng)前新索引項時，就需要進行索引頁的分裂；
如果空間足夠，則直接插入即可；

頁面分裂

Btree的頁面分裂是插入環(huán)節(jié)中的關(guān)鍵點，也是難點所在；在這個環(huán)節(jié)中，因為會修改多個節(jié)點頁，對并發(fā)訪問影響比較大，postgresql在這里做了一些優(yōu)化；

我們先按常規(guī)思路來模擬一下分裂的過程；
某一節(jié)點分裂成左右兩個節(jié)點，將舊節(jié)點的內(nèi)容平分到新節(jié)點中，然后變更左節(jié)點的后續(xù)鏈接，變更右節(jié)點的前續(xù)和后續(xù)鏈接，將它中加入本層的雙向鏈表，最后將新增節(jié)點信息加到父節(jié)點中；

這樣一個分裂的過程中，所有變更節(jié)點都需要加互斥鎖。在btree查找章節(jié)中已經(jīng)介紹過，上下層之間是單向的，也就是只能從父節(jié)點找到下層節(jié)點，為了避免重復(fù)查找父節(jié)點，在確定插入節(jié)點時，就已經(jīng)將路的層次路徑記了下來；

下面我們來看postgresql中如何進行分裂，以及進行了那些地方的優(yōu)化；

按分裂的節(jié)點類型，分為根節(jié)點，頁子節(jié)點，中間branch節(jié)點的分裂；

根頁面的分裂

在一開始，數(shù)據(jù)不多時，根頁面節(jié)點就足夠存下了，此時根節(jié)點也是葉子節(jié)點；隨著數(shù)據(jù)的增多，根節(jié)點就需要分裂了。

它的分裂不同于其它類型，下面圖示分析：

當(dāng)root節(jié)點分裂時：

1.節(jié)點分裂

• 先加鎖待分裂的root節(jié)點；
• 在本地內(nèi)存中生成一個left節(jié)點，將它的btpo_flags設(shè)置為分裂中，并且插入highkey，也就是右節(jié)點的最小值；
• 在索引文件中生成right節(jié)點，注意這里是直接在索引文件中增加一個節(jié)點，同時加互斥鎖；設(shè)置right節(jié)點的前繼為待分裂的root節(jié)點，后繼為空，因為它是最右的節(jié)點；
• 將舊root中的數(shù)據(jù)根據(jù)劃分位置，分別移動到左右兩個節(jié)點中；并且將待插入值插入合適位置，因為是分裂，所以一定是有空閑空間的，所以在此處直接插入；
• 將left節(jié)點拷到待分裂節(jié)點中；這樣，left，right節(jié)點都在索引文件中了；
• 將left,right頁面標(biāo)臟，同時更新待分裂節(jié)點的右節(jié)點的前繼為right節(jié)點，并生成分裂的WAL；
• 解鎖待分裂節(jié)點的右節(jié)點；

2.更新父節(jié)點

• 然后新創(chuàng)建一個root節(jié)點，將左右節(jié)點的信息插入新的root節(jié)點中；
• 將left節(jié)點的正在分裂標(biāo)志取消；
• 新root節(jié)點頁面標(biāo)臟，以及生成新root頁面修改的WAL；
• 解鎖root,left,right節(jié)點；

在通過pginspect插件看時，就會發(fā)現(xiàn)root節(jié)點的pageno隨著數(shù)據(jù)增加會一直變動，其實就是樹的層次在增加，每增加一層級時，就會新創(chuàng)建一個root頁面；

葉子頁面分裂

頁子節(jié)點頁面的分裂，是最常見的一種，當(dāng)然也經(jīng)過了很多的優(yōu)化，比如對于相同鍵值的數(shù)據(jù)；還有對于多版本跨節(jié)點存儲時，會再插入一條索引項，還有對于NULL值的存儲；

先來看一下葉子頁面分裂的整體流程示意圖：

葉子節(jié)點分裂如下：

1.節(jié)點分裂

• 加鎖待分裂節(jié)點；
• 在本地內(nèi)存中生成一個left節(jié)點，將它的btpo_flags設(shè)置為分裂中，并且插入highkey，也就是右節(jié)點的最小值；
• 在索引文件中生成right節(jié)點，注意這里是直接在索引文件中增加一個節(jié)點，同時加互斥鎖；設(shè)置right節(jié)點的前繼為待分裂的root節(jié)點，后繼為空，因為它是最右的節(jié)點；
• 將舊root中的數(shù)據(jù)根據(jù)劃分位置，分別移動到左右兩個節(jié)點中；并且將待插入值插入合適位置，因為是分裂，所以一定是有空閑空間的，所以在此處直接插入；
• 將left節(jié)點拷到待分裂節(jié)點中；這樣，left，right節(jié)點都在索引文件中了；
• 將left,right頁面標(biāo)臟，同時更新待分裂節(jié)點的右節(jié)點的前繼為right節(jié)點，并生成分裂的WAL；
• 解鎖待分裂節(jié)點的右節(jié)點；

2.更新父節(jié)點

• 加鎖待分裂節(jié)點的父節(jié)點，然后解鎖右節(jié)點；這一步解鎖也很關(guān)鍵，優(yōu)化了并發(fā)性能；
• 將右節(jié)點信息，也就是左節(jié)點的highkey值, 插入父節(jié)點中; 當(dāng)然這一步可能會遞歸進行,因為父節(jié)點有可能還會進行分裂，直到root再次分裂，就會增加樹的層次；
• 生成父節(jié)點變動的WAL；
• 解鎖父節(jié)點，left節(jié)點；

branch頁面分裂

branch節(jié)點，是一種btree中間層的節(jié)點類型，它們存儲的都是下層索引節(jié)點的頁面位置和對應(yīng)頁面上的最小值；只有葉子節(jié)點上才會存儲數(shù)據(jù)頁的信息；

branch節(jié)點的分裂，類似于葉子節(jié)點的分裂；

只是在更新父節(jié)點時，多了一步，將left節(jié)點的正在分裂標(biāo)志取消，也就是對于中間層的分裂已經(jīng)完成；

新索引項加入

如果不發(fā)生分裂，那么插入的流程如下：

• 找到索引插入位置；
• 索引項插入頁面，并給當(dāng)前頁面置臟標(biāo)記；
• 更新meta頁的fastroot；如果樹的某一層只有一個節(jié)點時，這個節(jié)點就是fastroot，記錄到meta頁面，下次遍歷時，直接從fastroot開始掃描；
• 檢查是否需要記錄fastpath對應(yīng)的塊，也就是葉子節(jié)點最右節(jié)點；

索引頁面插入

因為btree索引是一種有序的索引，也是存儲有序的，所以增加一條索引項時，如果在插入位置沒有空槽位，就需要將當(dāng)前位置及后面的索引項，向后移一個槽位，再將新索引項插入；

并發(fā)控制

在整個插入過程中，查找過程，還有分裂時持有多個塊的情況進行了優(yōu)化；

主要通過以下措施：

掃描和插入時

這兩個過程中，只會對當(dāng)前頁面加鎖；
在索引掃描時，結(jié)束一個索引頁面就會釋放，再加下一個索引頁面加鎖，這樣保持了很好的并發(fā)訪問性能；
索引項只記錄向下的關(guān)系，所以在掃描過程中，會記錄父子關(guān)系的stack，這方便在分裂時，向上遞歸；

索引分裂

在分裂的時候，會加多個節(jié)點的鎖，加鎖原則是從左到右，避免死鎖發(fā)生；

分裂時減少了加鎖的節(jié)點數(shù)量，從葉子節(jié)點開始，葉子頁面分裂時，會加左節(jié)點和右節(jié)點的鎖；當(dāng)更新父節(jié)點時，加鎖父節(jié)點后，就釋放了右節(jié)點的鎖；整個過程中持有的鎖，可能最多就是三個節(jié)點，當(dāng)然還有短暫持有的鎖，如meta節(jié)點，還有待分裂節(jié)點的右節(jié)點的鎖，最多時會有四個節(jié)點；

fastpath

記錄葉子層的rightmost，對于null直接插入還有批量順序插入時，直接就可以從fastpath找到插入節(jié)點，也就是葉子節(jié)點的最右節(jié)點；如果不符合時，再遍歷查找；
這里使用了條件鎖，得不到時，也會進行遍歷查找，增加并發(fā)訪問性能；

fastroot

當(dāng)樹的某一層只有一個節(jié)點時，那這個節(jié)點就是fastroot，不用從root進行遍歷，而從fastroot遍歷就可以，加快速度；

對于異常的保護

因為索引頁面不像數(shù)據(jù)頁面是多版本機制，為了保持索引的存儲精煉，而采用了原地更新，這就需要在更新時，如果服務(wù)異外宕機了，數(shù)據(jù)還能保持一致性和完整性；

在插入時的保護

如果沒有發(fā)生頁面分裂，在插入數(shù)據(jù)時發(fā)生了異常，此時是由WAL來恢復(fù)；WAL記錄了插入的位置，以及原有數(shù)據(jù)位置的變化；

在分裂時的保護

首先在分裂時，開始只將右節(jié)點加入了索引文件，分裂節(jié)點的數(shù)據(jù)并沒有發(fā)生變化；此時異常并不會影響；

接下來，分裂節(jié)點數(shù)據(jù)發(fā)生變化，此時它的flag還是正在分裂中，那么數(shù)據(jù)其實是完整的，分別在左右兩個頁面上，只是從父節(jié)上只能找到左節(jié)點，從左節(jié)點再順序通過后繼鏈表就可以找到右節(jié)點，這在前面btree索引查找時就分享過。

結(jié)尾

非常感謝大家的支持，在瀏覽的同時別忘了留下您寶貴的評論，如果覺得值得鼓勵，請點贊，收藏，我會更加努力！

作者郵箱：study@senllang.onaliyun.com
如有錯誤或者疏漏歡迎指出，互相學(xué)習(xí)。

注：未經(jīng)同意，不得轉(zhuǎn)載！文章來源地址http://www.zghlxwxcb.cn/news/detail-717532.html

到了這里，關(guān)于postgresql 內(nèi)核源碼分析 btree索引插入分析，索引頁面分裂流程，多舉措進行并發(fā)優(yōu)化，對異常進行保護處理的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！