2011-09-03 66 views
0

作爲一種學習練習,我試圖在C#中編寫一個簡單的嵌入式數據庫。一切都很順利,但我將數據保存到磁盤時遇到困難。數據如何在數據庫的數據文件中組織

作爲我的一個問題的例子..我可能需要「插入」數據到數據文件的中間。這對於順序文件訪問顯然是不可能的。出於明顯的性能原因,每次插入時重新寫入整個文件的後半部分不是一種選擇。

我能想象的唯一解決方案是編寫每個表,然後在文件中留出一些空白空間。空的空間將用於寫入新的數據,並且每次表使用其可用空間時,文件都需要重構/增長。

我想我的問題是......究竟是什麼數據在一個典型的DB數據文件中「看起來像」?新文件如何/在哪裏寫入文件?

回答

2

通常數據庫將使用B樹來存儲數據(其中鍵將作爲該行的主鍵,並且該值將是該行的內容)和索引。這樣您就可以在O(log n)時間將行插入任意位置。

例如,請參閱file format for SQLite databases,其中描述了SQLite如何使用B樹,其中內部節點僅存儲指針,葉節點僅存儲數據。

另請參閱:http://en.wikipedia.org/wiki/B-tree#Insertions_and_deletions_cause_trouble,這似乎解決您遇到的問題。

0

David Wolever的答案是錯誤的。數據庫的數據不存儲在B樹中。 B樹(通常是B +樹)只存儲內部節點中的鍵和子指針以及葉節點中的鍵和數據指針。 B +樹通常不存儲數據(他們可能會爲關係表做這些)。數據庫的數據存儲在數據文件中,這些數據文件是以塊的形式組織的。