數(shù)據(jù)庫并發(fā)訪問樹協(xié)議

?專欄內(nèi)容：

• 手寫數(shù)據(jù)庫toadb
  本專欄主要介紹如何從零開發(fā)，開發(fā)的步驟，以及開發(fā)過程中的涉及的原理，遇到的問題等，讓大家能跟上并且可以一起開發(fā)，讓每個需要的人成為參與者。
  本專欄會定期更新，對應的代碼也會定期更新，每個階段的代碼會打上tag，方便階段學習。

?開源貢獻：

• toadb開源庫

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

前言

隨著信息技術的飛速發(fā)展，數(shù)據(jù)已經(jīng)滲透到各個領域，成為現(xiàn)代社會最重要的資產(chǎn)之一。在這個大數(shù)據(jù)時代，數(shù)據(jù)庫理論在數(shù)據(jù)管理、存儲和處理中發(fā)揮著至關重要的作用。然而，很多讀者可能對數(shù)據(jù)庫理論感到困惑，不知道如何選擇合適的數(shù)據(jù)庫，如何設計有效的數(shù)據(jù)庫結構，以及如何處理和管理大量的數(shù)據(jù)。因此，本專欄旨在為讀者提供一套全面、深入的數(shù)據(jù)庫理論指南，幫助他們更好地理解和應用數(shù)據(jù)庫技術。

數(shù)據(jù)庫理論是研究如何有效地管理、存儲和檢索數(shù)據(jù)的學科。在現(xiàn)代信息化社會中，數(shù)據(jù)量呈指數(shù)級增長，如何高效地處理和管理這些數(shù)據(jù)成為一個重要的問題。同時，隨著云計算、物聯(lián)網(wǎng)、大數(shù)據(jù)等新興技術的不斷發(fā)展，數(shù)據(jù)庫理論的重要性日益凸顯。

因此，本專欄的分享希望可以提高大家對數(shù)據(jù)庫理論的認識和理解，對于感興趣的朋友帶來幫助。

概述

有一類數(shù)據(jù)庫元素，它的組織結構是樹的形式，樹中的各元素之間沒有包含關系，如B-樹索引數(shù)據(jù)的組織形式，對于此類數(shù)據(jù)的訪問必須從樹進行查找訪問，這與之前介紹的數(shù)據(jù)庫元素的層次結構，在加鎖方式上不一樣。

本文將重點介紹樹形結構組織的數(shù)據(jù)的訪問規(guī)則，封鎖原理，以及一些優(yōu)化的談討。

樹結構的封鎖不同點

• 訪問需要加鎖； 在訪問樹形數(shù)據(jù)時，假如是B-樹索引，為了保持讀寫操作的可串行化，需要進行封鎖訪問，鎖模式如之前提到的讀鎖，寫鎖，更新鎖；

• 加鎖粒度為節(jié)點；樹的每個節(jié)點也是一個數(shù)據(jù)塊，加鎖粒度也是節(jié)點，更小到元組會帶來更多不利，更大的粒度到整棵樹，那幾乎沒有并發(fā)性了；

• 加鎖方式與2PL有區(qū)別；樹的訪問都是從根開始，然后一層層遍歷，找到對應節(jié)點位置；那么加鎖也從根開始，按之前介紹的兩階段鎖規(guī)則，在使用前不能釋放鎖，那就意味著根節(jié)點沒有并發(fā)性，這不利用索引的使用效率。如果確定不修改樹節(jié)點，那么就可以提前釋放根節(jié)點的鎖，這就有悖2PL；

基于以上不同，對于樹形組織的數(shù)據(jù)，專門使用樹協(xié)議加鎖方式，而不是2PL方式加鎖，在確定當前節(jié)點還有空間時，就不會修改根節(jié)點，此時就可以提前釋放根節(jié)點的鎖，同樣適用于中間節(jié)點，當然串行化的保證依賴于都從根往下順次查找這一順序。

樹協(xié)議的規(guī)則

樹協(xié)議由以下規(guī)則構成，假定訪問樹結構使用一種鎖，用L(X)來表示加鎖X節(jié)點；

• 訪問樹結構時，第一個鎖可以加在樹中的任意節(jié)點；

• 只有持有父節(jié)點的鎖時，才能對其后續(xù)節(jié)點加鎖；

• 事務可以在任何時候解鎖；

• 不能對已解鎖的節(jié)點重新加鎖，即使此時持有父節(jié)點的鎖也不行；

舉例

并發(fā)三個事務，T1 從節(jié)點A開始移動，經(jīng)過B，C，D；事務T2從B開始，目標是E節(jié)點；事務T3從E開始，移動到F和G；其中加鎖是L(X),解鎖是U(X)表示。

這個例子中，事務T1，T2，T3是按照樹協(xié)議進行并發(fā)調(diào)度，其中T2在加鎖E節(jié)點時，與T3節(jié)點發(fā)生沖突，導致它被延遲，在T3釋放E節(jié)點鎖之后又得以繼續(xù)執(zhí)行。

樹協(xié)議原理分析

樹協(xié)議在調(diào)度中，鎖涉及的事務中的必然包含一個串行動作序列，因為它們都是從上到下的訪問順序，這個可以用優(yōu)先圖來證明，如果優(yōu)先圖中沒有環(huán)的存在，說明它等價一個可串行化的調(diào)度。

通過上面協(xié)議規(guī)則和樹的訪問順序，在一棵樹中，兩個事務并發(fā)時，可以得出以下判斷；

• 假如有幾個節(jié)點，兩個事務都需要加鎖，那么這幾個節(jié)點上的加鎖順序是一樣的；

因為兩個事務訪問的公共元素有兩個或兩個以上時，每個事務加鎖的節(jié)點可以組成一個子樹，兩個子樹的交也是一棵子樹，訪問時也是從最高節(jié)點開始，依次向下加鎖，所有公共元素的加鎖順序是一致。

總結

對于樹形組織的并發(fā)訪問的控制，不能使用兩階段鎖的模式，為了提升并發(fā)訪問效率，通過樹協(xié)議，可以提前釋放當前節(jié)點路徑上的鎖。

結尾

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

作者郵箱：study@senllang.onaliyun.com
如有錯誤或者疏漏歡迎指出，互相學習。文章來源地址http://www.zghlxwxcb.cn/news/detail-764749.html

到了這里，關于【數(shù)據(jù)庫】樹形數(shù)據(jù)組織架構下的封鎖并發(fā)控制，B樹索引并發(fā)訪問控制，樹協(xié)議原理及案例分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！