自己寫(xiě)一個(gè)簡(jiǎn)單的數(shù)據(jù)庫(kù)， 原理 大概有以下幾點(diǎn)： 一、數(shù)據(jù)以文本形式保存 將所要保存的數(shù)據(jù)寫(xiě)入文本文件，這個(gè)文本文件就是數(shù)據(jù)庫(kù)。 為了方便讀取，數(shù)據(jù)必須分為記錄，每一條記錄的長(zhǎng)度規(guī)定為等長(zhǎng)。 舉例：假定每條記錄的長(zhǎng)度是800字節(jié)，那么第5條記錄的開(kāi)

自己寫(xiě)一個(gè)簡(jiǎn)單的數(shù)據(jù)庫(kù)，原理大概有以下幾點(diǎn)：

一、數(shù)據(jù)以文本形式保存

將所要保存的數(shù)據(jù)寫(xiě)入文本文件，這個(gè)文本文件就是數(shù)據(jù)庫(kù)。

為了方便讀取，數(shù)據(jù)必須分為記錄，每一條記錄的長(zhǎng)度規(guī)定為等長(zhǎng)。

舉例：假定每條記錄的長(zhǎng)度是800字節(jié)，那么第5條記錄的開(kāi)始位置就在3200字節(jié)。

大多數(shù)的時(shí)候我們不知道某一條記錄在第幾個(gè)位置，只知道主鍵的值。這時(shí)為了讀取數(shù)據(jù)，可以一條條比對(duì)記錄。但是這樣做的效率太低。實(shí)際應(yīng)用中，數(shù)據(jù)庫(kù)往往采用B樹(shù)格式存儲(chǔ)數(shù)據(jù)。

二、關(guān)于B樹(shù)

要理解B樹(shù)先需要理解二叉查找樹(shù)

說(shuō)二叉查找樹(shù)是一種查找效率非常高的數(shù)據(jù)結(jié)構(gòu)，它有三個(gè)特點(diǎn)：

(1)每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子樹(shù)。

(2)左子樹(shù)都為小于父節(jié)點(diǎn)的值，右子樹(shù)都為大于父節(jié)點(diǎn)的值。

(3)在n個(gè)節(jié)點(diǎn)中找到目標(biāo)值，一般只需要log(n)次比較。

二叉查找樹(shù)的結(jié)構(gòu)不適合數(shù)據(jù)庫(kù)，因?yàn)樗牟檎倚逝c層數(shù)有關(guān)。越處在下層的數(shù)據(jù)，就需要越多次的比較。極端的情況下，n個(gè)數(shù)據(jù)需要n次比較才能找到目標(biāo)值。對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)，每進(jìn)入一層，就要從硬盤(pán)讀取一次數(shù)據(jù)，這非常致命，因?yàn)橛脖P(pán)的讀取時(shí)間遠(yuǎn)遠(yuǎn)大于數(shù)據(jù)處理時(shí)間，數(shù)據(jù)庫(kù)讀取硬盤(pán)的次數(shù)越少越好。

B樹(shù)是對(duì)二叉查找樹(shù)的改進(jìn)。它的設(shè)計(jì)思想是，將相關(guān)數(shù)據(jù)盡量集中在一起，以便一次讀取多個(gè)數(shù)據(jù)，減少硬盤(pán)操作次數(shù)。

B樹(shù)的特點(diǎn)：

(1)一個(gè)節(jié)點(diǎn)可以容納多個(gè)值。

(2)除非數(shù)據(jù)已經(jīng)填滿，否則不會(huì)增加新的層，也就是說(shuō)，B樹(shù)追求“層”越少越好。

(3)子節(jié)點(diǎn)的值，與父節(jié)點(diǎn)中的值有嚴(yán)格的大小對(duì)應(yīng)關(guān)系。一般來(lái)說(shuō)，如果父節(jié)點(diǎn)有a個(gè)值，那么就有a+1個(gè)子節(jié)點(diǎn)。比如上圖中，父節(jié)點(diǎn)有兩個(gè)值(7和16),就應(yīng)對(duì)應(yīng)三個(gè)子節(jié)點(diǎn)，第一個(gè)子節(jié)點(diǎn)都是小于7的值，最后一個(gè)子節(jié)點(diǎn)都是大于16的值，中間的子節(jié)點(diǎn)就是7和16之間的值。

這種數(shù)據(jù)結(jié)構(gòu)非常有利于減少讀取硬盤(pán)的次數(shù)。假定一個(gè)節(jié)點(diǎn)可以容納100個(gè)值，那么3層的B樹(shù)可以容納100萬(wàn)個(gè)數(shù)據(jù)，如果換成二叉查找樹(shù)，則需要20層。假定操作系統(tǒng)一次讀取一個(gè)節(jié)點(diǎn)，并且根節(jié)點(diǎn)保留在內(nèi)存中，那么B樹(shù)在100萬(wàn)個(gè)數(shù)據(jù)中查找目標(biāo)值，只需要讀取兩次硬盤(pán)。

三、索引

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

所謂索引，就是以某個(gè)字段為關(guān)鍵字的B樹(shù)文件，假定一張“雇員表”，包含了員工號(hào)(主鍵)和姓名兩個(gè)字段，可以對(duì)姓名建立索引文件，該文件以B樹(shù)格式對(duì)姓名進(jìn)行存儲(chǔ)，每個(gè)姓名后面是其在數(shù)據(jù)庫(kù)中的位置(即第幾條記錄)。查找姓名的時(shí)候，先從索引中找到對(duì)應(yīng)的第幾條記錄，然后再?gòu)谋砀裰凶x取。這種索引查找方法，叫做“索引順序存取方法”，縮寫(xiě)為ISAM。它已經(jīng)有多種實(shí)現(xiàn)，只要使用這些代碼庫(kù)，就能自己寫(xiě)一個(gè)最簡(jiǎn)單的數(shù)據(jù)庫(kù)。

四、高級(jí)功能

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

(1)SQL語(yǔ)言是數(shù)據(jù)庫(kù)通用操作語(yǔ)言，所以需要一個(gè)SQL解析器，將SQL命令解析為對(duì)應(yīng)的ISAM操作。

(2)數(shù)據(jù)庫(kù)連接(join)是指數(shù)據(jù)庫(kù)的兩張表通過(guò)“外鍵”，建立連接關(guān)系。你需要對(duì)這種操作進(jìn)行優(yōu)化。

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

(4)備份機(jī)制：保存數(shù)據(jù)庫(kù)的副本。

(5)遠(yuǎn)程操作：使得用戶可以在不同的機(jī)器上，通過(guò)TCP/IP協(xié)議操作數(shù)據(jù)庫(kù)。

部分內(nèi)容來(lái)自點(diǎn)擊打開(kāi)鏈接，后續(xù)依然會(huì)不斷更新完善。

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com