數據庫的最簡單實現

legendaryedu 發布于2019-06-25 18:13 / 3161人閱讀

摘要：二叉查找樹是一種查找效率非常高的數據結構，它有三個特點。二叉查找樹的結構不適合數據庫，因為它的查找效率與層數相關。樹是對二叉查找樹的改進。備份機制保存數據庫的副本。

轉載自:阮一峰的網絡日志

所有應用軟件之中，數據庫可能是最復雜的。
MySQL的手冊有3000多頁，PostgreSQL的手冊有2000多頁，Oracle的手冊更是比它們相加還要厚。
但是，自己寫一個最簡單的數據庫，做起來并不難。Reddit上面有一個帖子，只用了幾百個字，就把原理講清楚了。下面是我根據這個帖子整理的內容。

數據以文本形式保存

第一步，就是將所要保存的數據，寫入文本文件。這個文本文件就是你的數據庫。
為了方便讀取，數據必須分成記錄，每一條記錄的長度規定為等長。比如，假定每條記錄的長度是800字節，那么第5條記錄的開始位置就在3200字節。
大多數時候，我們不知道某一條記錄在第幾個位置，只知道主鍵（primary key）的值。這時為了讀取數據，可以一條條比對記錄。但是這樣做效率太低，實際應用中，數據庫往往采用B樹（B-tree）格式儲存數據。

什么是B樹？

要理解B樹，必須從二叉查找樹（Binary search tree）講起。

二叉查找樹是一種查找效率非常高的數據結構，它有三個特點。

1. 每個節點最多只有兩個子樹。
2. 左子樹都為小于父節點的值，右子樹都為大于父節點的值。
3. 在n個節點中找到目標值，一般只需要log(n)次比較。

二叉查找樹的結構不適合數據庫，因為它的查找效率與層數相關。越處在下層的數據，就需要越多次比較。極端情況下，n個數據需要n次比較才能找到目標值。對于數據庫來說，每進入一層，就要從硬盤讀取一次數據，這非常致命，因為硬盤的讀取時間遠遠大于數據處理時間，數據庫讀取硬盤的次數越少越好。
B樹是對二叉查找樹的改進。它的設計思想是，將相關數據盡量集中在一起，以便一次讀取多個數據，減少硬盤操作次數。

B樹的特點也有三個。

1. 一個節點可以容納多個值。比如上圖中，最多的一個節點容納了4個值。
2. 除非數據已經填滿，否則不會增加新的層。也就是說，B樹追求"層"越少越好。
3. 子節點中的值，與父節點中的值，有嚴格的大小對應關系。一般來說，如果父節點有a個值，那么就有a+1個子節點。比如上圖中，父節點有兩個值（7和16），就對應三個子節點，第一個子節點都是小于7的值，最后一個子節點都是大于16的值，中間的子節點就是7和16之間的值。

  這種數據結構，非常有利于減少讀取硬盤的次數。假定一個節點可以容納100(a)個值，那么3(n)層的B樹最大可以容納1030300((a+1)^(n-1)*a)個數據，如果換成二叉查找樹，則需要20層！假定操作系統一次讀取一個節點，并且根節點保留在內存中，那么B樹在100萬個數據中查找目標值，只需要讀取兩次硬盤。

索引

數據庫以B樹格式儲存，只解決了按照"主鍵"查找數據的問題。如果想查找其他字段，就需要建立索引（index）。
所謂索引，就是以某個字段為關鍵字的B樹文件。假定有一張"雇員表"，包含了員工號（主鍵）和姓名兩個字段。可以對姓名建立索引文件，該文件以B樹格式對姓名進行儲存，每個姓名后面是其在數據庫中的位置（即第幾條記錄）。查找姓名的時候，先從索引中找到對應第幾條記錄，然后再從表格中讀取。
這種索引查找方法，叫做"索引順序存取方法"（Indexed Sequential Access Method），縮寫為ISAM。它已經有多種實現（比如C-ISAM庫和D-ISAM庫），只要使用這些代碼庫，就能自己寫一個最簡單的數據庫。

高級功能

部署了最基本的數據存取（包括索引）以后，還可以實現一些高級功能。
（1）SQL語言是數據庫通用操作語言，所以需要一個SQL解析器，將SQL命令解析為對應的ISAM操作。
（2）數據庫連接（join）是指數據庫的兩張表通過"外鍵"，建立連接關系。你需要對這種操作進行優化。
（3）數據庫交易（transaction）是指批量進行一系列數據庫操作，只要有一步不成功，整個操作都不成功。所以需要有一個"操作日志"，以便失敗時對操作進行回滾。
（4）備份機制：保存數據庫的副本。
（5）遠程操作：使得用戶可以在不同的機器上，通過TCP/IP協議操作數據庫。
（完）

GPU云服務器云服務器簡單cdn部署實現實現簡單計算器 php簡單實現mvc js實現的簡單特效

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/17449.html

你想不到的最簡單php操作MySQL

摘要：千鋒出品之天龍八部操作必須先開啟擴展函數庫首先先開啟開啟成功呢我就可以開始連接數據庫了，第一步連接數據庫服務器地址用戶名，密碼第二步判斷連接數據庫是否成功連接錯誤號連接錯誤信息第三步選擇數據庫數據庫名稱第四步設置字符集第五步準備語句表名第六　千鋒PHP出品之天龍八部：　Php操作mysql必須先開啟mysq擴展函數庫　　首先先開啟extension = mysqli_dll; 　　...

pkhope 2019-06-27 16:12 評論0 收藏0
單源點最短路徑(Bellman-Ford)原理及js實現

摘要：說明算法運行結束后，會得到從源節點到其它所有節點的最短路徑，同時得到每個節點的前驅節點，不能包含負權回路如圖但可以包含圖，這里所說的負權環路是指環路的權值總和為正或為負圖圖松弛操作概念松弛操作針對的操作對象是圖中的邊，對圖中任意一條邊， 1. 說明 Bellman-Ford算法運行結束后，會得到從源節點 s 到其它所有節點的最短路徑，同時得到每個節點的前驅節點，Bellman-Ford...

Michael_Lin 2019-08-21 18:37 評論0 收藏0