實現一個微型數據庫

自己寫一個簡單的數據庫， 原理 大概有以下幾點： 一、數據以文本形式保存 將所要保存的數據寫入文本文件，這個文本文件就是數據庫。 為了方便讀取，數據必須分為記錄，每一條記錄的長度規定為等長。 舉例：假定每條記錄的長度是800字節，那么第5條記錄的開

自己寫一個簡單的數據庫，原理大概有以下幾點：

一、數據以文本形式保存

將所要保存的數據寫入文本文件，這個文本文件就是數據庫。

為了方便讀取，數據必須分為記錄，每一條記錄的長度規定為等長。

舉例：假定每條記錄的長度是800字節，那么第5條記錄的開始位置就在3200字節。

大多數的時候我們不知道某一條記錄在第幾個位置，只知道主鍵的值。這時為了讀取數據，可以一條條比對記錄。但是這樣做的效率太低。實際應用中，數據庫往往采用B樹格式存儲數據。

二、關于B樹

要理解B樹先需要理解二叉查找樹

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

(1)每個節點最多只有兩個子樹。

(2)左子樹都為小于父節點的值，右子樹都為大于父節點的值。

(3)在n個節點中找到目標值，一般只需要log(n)次比較。

二叉查找樹的結構不適合數據庫，因為他的查找效率與層數有關。越處在下層的數據，就需要越多次的比較。極端的情況下，n個數據需要n次比較才能找到目標值。對于數據庫來說，每進入一層，就要從硬盤讀取一次數據，這非常致命，因為硬盤的讀取時間遠遠大于數據處理時間，數據庫讀取硬盤的次數越少越好。

B樹是對二叉查找樹的改進。它的設計思想是，將相關數據盡量集中在一起，以便一次讀取多個數據，減少硬盤操作次數。

B樹的特點：

(1)一個節點可以容納多個值。

(2)除非數據已經填滿，否則不會增加新的層，也就是說，B樹追求“層”越少越好。

(3)子節點的值，與父節點中的值有嚴格的大小對應關系。一般來說，如果父節點有a個值，那么就有a+1個子節點。比如上圖中，父節點有兩個值(7和16),就應對應三個子節點，第一個子節點都是小于7的值，最后一個子節點都是大于16的值，中間的子節點就是7和16之間的值。

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

三、索引

數據庫以B樹格式存儲，只解決了按照“主鍵”查找數據的問題。如果想查找其他字段，就需要建立檢索(index)。

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

四、高級功能

部署了最基本的數據存取(包括索引)以后，還可以實現一些高級功能。

(1)SQL語言是數據庫通用操作語言，所以需要一個SQL解析器，將SQL命令解析為對應的ISAM操作。

(2)數據庫連接(join)是指數據庫的兩張表通過“外鍵”，建立連接關系。你需要對這種操作進行優化。

(3)數據庫事務(transaction)是指批量進行一系列數據庫操作，只要有一步不成功，整個操作都不成功。所以需要有一個“操作日志”，以便失敗時對操作進行回滾。

(4)備份機制：保存數據庫的副本。

(5)遠程操作：使得用戶可以在不同的機器上，通過TCP/IP協議操作數據庫。

部分內容來自點擊打開鏈接，后續依然會不斷更新完善。

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com