實現一個簡單Database7

来源:https://www.cnblogs.com/greatsql/archive/2022/11/02/16852096.html
-Advertisement-
Play Games

GreatSQL社區原創內容未經授權不得隨意使用,轉載請聯繫小編並註明來源。 GreatSQL是MySQL的國產分支版本,使用上與MySQL一致。 前文回顧 實現一個簡單的Database1(譯文) 實現一個簡單的Database2(譯文) 實現一個簡單的Database3(譯文) 實現一個簡單的D ...


  • GreatSQL社區原創內容未經授權不得隨意使用,轉載請聯繫小編並註明來源。
  • GreatSQL是MySQL的國產分支版本,使用上與MySQL一致。

前文回顧

實現一個簡單的Database1(譯文)

實現一個簡單的Database2(譯文)

實現一個簡單的Database3(譯文)

實現一個簡單的Database4(譯文)

實現一個簡單的Database5(譯文)

實現一個簡單的Database6(譯文)


譯註:cstsck在github維護了一個簡單的、類似sqlite的資料庫實現,通過這個簡單的項目,可以很好的理解資料庫是如何運行的。本文是第七篇,主要是對B-tree的介紹

Part 7 B-Tree簡介

B-tree是SQLite用來表示表和索引的數據結構,所以B-tree是非常中心的想法。這個主題主要是介紹B-tree數據結構,所以不會有任何的代碼。

為什麼說對於資料庫來說,樹是非常好的數據結構呢?

  • 查找特定的value很快(對數時間花銷,loga N)
  • 插入一行或者對查詢到的數據刪除很快(再平衡使用常量時間)
  • 遍歷一個範圍內的value很快(不像hash map)

B-tree不同於二叉樹(“B”可能代表發明人的名字,但也可以代表“Balanced”)。這裡是一個B-tree例子:

download

B-Tree 例子(https://en.wikipedia.org/wiki/File:B-tree.svg)

不像二叉樹每個節點只能有兩個子節點,B-tree的每個節點可以有兩個以上的子節點。每個節點最多可以有 m 個子節點,其中 m 叫做樹的“order”(或者叫“階”)。為了保持樹的儘量平衡,我們還要求節點必須至少有 m / 2 個子節點(四捨五入)。

但還有一些例外:

  • 葉子節點沒有子節點
  • 根節點的子節點數可以少於 m,但至少要有兩個
  • 如果根節點也是葉子節點(樹只有一個節點),那它有0個子節點

上面的描述的是一個B-tree,SQLite用它來存儲索引。為了存儲表數據,SQLites使用一種B-tree的變體,稱為B+tree。

B-tree B+ tree
發音 “Bee Tree” “Bee Plus Tree”
用來存儲 索引
內部節點是否存儲key
內部節點是否存儲value
每個節點的子節點數
內部節點 vs 葉子節點 相同結構 不同結構

在我們開始實現索引之前,我將只討論B+tree,但這裡將其稱為 B-tree 或者 btree。

有子節點(children)的節點被稱為“內部”節點(internal node),內部節點和葉子節點在結構上不同:

m階tree 內部節點 葉子節點
存儲 key和指向子節點的指針 key和value
key的數目 最多m-1個 越多越好
指針的數目 keys + 1
value的數目 與key的數目相同
Key的用途 用來路由 與value成對存儲
存儲value?

這裡通過一個例子來看一下,當插入一個元素時,B-tree是怎樣發生結構變化的。為了讓事情看起來更容易理解,這棵B-tree的階(order)設置為3(m=3),也就是說:

  • 每個內部節點最多有三個子節點(m)
  • 每個內部節點最多有兩個key
  • 每個內部節點至少兩個子節點(m-1)
  • 每個內部節點至少一個key

一棵空樹只有一個節點:根節點。根節點最開始也作為葉子節點,有0個鍵值對(key/value):

download

空的btree
如果我們插入兩個鍵值對(超過兩個鍵值對,節點需要分裂,參考上面規則),他們會按順序排序存放在葉子節點中。

download

一個節點的btree
我們假設了節點的容量是兩個鍵值對兒。當我們插入另外一個的時候,就不得不分裂葉子節點了,分裂後的兩個節點每個存放之前一半的鍵值對。分裂後的兩個節點都變成了內部節點,同時也變成了一個新的節點的子節點,這個新的節點變成了根節點。

download

兩層的btree

圖中的內部節點(也是根節點)有一個key和兩個指針指向子節點(就是那兩條線)。如果我們想查找一個key,key小於或等於5,我們查看左子樹。如果查找的key大於5,就查看右子樹。

現在,準備插入一個新的key "2"。首先,我們查找它將位於哪個葉節點(如果它在樹中存在的話),這樣就到達了左側葉子節點。這個節點是滿的,所以把這個葉子節點進行分裂(split),併在父節點創建新的條目。

download

四節點的btree

現在繼續增加key,18 和 21 。現在又到了不得不分裂的情況,但是在父節點中已經沒有空間來增加新的鍵值對兒了。

download

內部節點沒有空間

解決方法就是分裂根節點為兩個內部節點,然後創建一個新的根節點作為兩個內部節點的父節點。

download

三層的btree

樹只是在我們分裂根節點的時候才會增加深度。每個葉子節點都有相同的深度和接近相同的數量的鍵值對兒,所以樹能夠保持平衡和快速的進行查找。

我暫時先不討論從樹中刪除鍵的操作,推遲到實現插入操作以後。

當我們實現這個數據結構時,每個節點都對應一個page。根節點將在page0中存在。節點中的子節點指針將簡單的使用包含子節點的page number。

下一次,我們開始實現btree。


Enjoy GreatSQL

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • CentOS6.x CentOS6中轉用Upstrat代替以前的init.d/rcX.d的線性啟動方式。 一、相關命令 通過initctl help可以查看相關命令 [root@localhost ~]# initctl help Job commands: start Start job. sto ...
  • 背景 2008 年前後的 Midori 項目試圖構建一個以 .NET 為用戶態基礎的操作系統,在這個項目中有很多讓 CLR 以及 C# 的類型系統向著適合系統編程的方向改進的探索,雖然項目最終沒有面世,但是積累了很多的成果。近些年由於 .NET 團隊在高性能和零開銷設施上的需要,從 2017 年開始 ...
  • 自己寫了一種,速度不是很快,但是能夠實現 var findpic = new FindPic(); var rec = findpic.FindPicture(@"C:\Users\zaranet\Desktop\xiao.png", @"C:\Users\zaranet\Desktop\da.pn ...
  • ###前言 剛接觸XAF的小伙伴可能會有一個疑惑,XAF中有Model(BusinessObject)、View、Controller,感覺明顯是一個MVC的設計模式,但當你用MVC的設計模式與其對應時,又會發現有一些不一樣,可能這時有小伙伴會想會不會是MVC的變體,因為MVC只是一個設計模式,不同 ...
  • 長連接與短連接 所謂長連接,指在一個TCP連接上可以連續發送多個數據包,在TCP連接保持期間,如果沒有數據包發送,需要雙方發檢測包以維持此連接,一般需要自己做線上維持。 短連接是指通信雙方有數據交互時,就建立一個TCP連接,數據發送完成後,則斷開此TCP連接,一般銀行都使用短連接。 比如http的, ...
  • <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-web ...
  • lsof -i tcp:埠號 要殺死進程的話,即:kill -9 pid ...
  • 前言 上一篇博客給大家介紹了LabVIEW開放神經網路交互工具包【ONNX】,今天我們就一起來看一下如何使用LabVIEW開放神經網路交互工具包實現TensorRT加速YOLOv5。 以下是YOLOv5的相關筆記總結,希望對大家有所幫助。 內容地址鏈接 【YOLOv5】LabVIEW+OpenVIN ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...