二進位檔案隨機存取是資料庫、索引、快取系統的基石。本文對比兩種經典實作：法一：固定長度記錄 + 記錄號直接定位 (適合記錄數固定、長度一致)；法二：讀入記憶體建立鏈表操作後寫回 (適合變長記錄、頻繁增刪)。附完整 C++ 範例專案 Random1 / Random2。
法一：固定記錄號直接定位 (Random1)
設計假設
- 每筆記錄固定大小
RECORD_SIZE (含結構體填補)。
- 記錄編號 (1-based) 對應檔案位移：
offset = (recNo - 1) * RECORD_SIZE。
- 新增 = 寫入指定位移 (覆寫或擴展)；刪除 = 標記旗標或縮減檔案 (需搬移後續記錄)。
核心類別 CFixedRecordFile
struct Record { int id; char name[32]; double score; bool deleted; }; // 固定 44 bytes
class CFixedRecordFile {
HANDLE hFile_; size_t recSize_;
public:
CFixedRecordFile(const wchar_t* path, size_t recSize) : recSize_(recSize) {
hFile_ = CreateFile(path, GENERIC_READ|GENERIC_WRITE, FILE_SHARE_READ, nullptr,
OPEN_ALWAYS, FILE_ATTRIBUTE_NORMAL, nullptr);
}
~CFixedRecordFile() { if (hFile_ != INVALID_HANDLE_VALUE) CloseHandle(hFile_); }
bool ReadRecord(DWORD recNo, Record& out) {
LARGE_INTEGER li; li.QuadPart = (LONGLONG)(recNo - 1) * recSize_;
SetFilePointerEx(hFile_, li, nullptr, FILE_BEGIN);
DWORD read; return ReadFile(hFile_, &out, recSize_, &read, nullptr) && read == recSize_;
}
bool WriteRecord(DWORD recNo, const Record& in) {
LARGE_INTEGER li; li.QuadPart = (LONGLONG)(recNo - 1) * recSize_;
SetFilePointerEx(hFile_, li, nullptr, FILE_BEGIN);
DWORD written; return WriteFile(hFile_, &in, recSize_, &written, nullptr) && written == recSize_;
}
bool AppendRecord(const Record& in) {
LARGE_INTEGER li; li.QuadPart = 0; SetFilePointerEx(hFile_, li, nullptr, FILE_END);
DWORD written; return WriteFile(hFile_, &in, recSize_, &written, nullptr) && written == recSize_;
}
DWORD GetRecordCount() {
LARGE_INTEGER size; GetFileSizeEx(hFile_, &size);
return (DWORD)(size.QuadPart / recSize_);
}
};
優缺點
| 優點 | 缺點 |
|---|
| O(1) 隨機讀寫，極快 | 記錄長度固定，浪費空間 (字串需定長) |
| 無需索引，邏輯簡單 | 刪除需搬移或留洞，碎片化 |
| 適合記錄數穩定、長度一致場景 | 動態增刪頻繁時效能差 |
法二：記憶體鏈表重組 (Random2)
設計假設
- 啟動時 整檔讀入記憶體，建立
std::list 或 std::vector>。
- 所有增刪改查在記憶體鏈表操作，O(1) 插入/刪除 (list) 或 O(n) 但緩存友好 (vector)。
- 關閉/存檔時 序列化整條鏈表寫回檔案 (可選擇二進位或文字格式)。
核心類別 CLinkedRecordFile
struct Record { int id; std::string name; double score; Record* next = nullptr; };
class CLinkedRecordFile {
std::list> records_;
std::wstring path_;
public:
CLinkedRecordFile(const wchar_t* path) : path_(path) { Load(); }
~CLinkedRecordFile() { Save(); }
void Load() {
// 二進位讀取：先讀記錄數，再逐筆讀取 (長度前綴字串)
// 或文字解析：每行一筆 CSV/JSON
}
void Save() {
// 依序寫入，重建檔案
}
void Add(int id, const std::string& name, double score) {
records_.push_back(std::make_unique(Record{id, name, score}));
}
bool Remove(int id) {
for (auto it = records_.begin(); it != records_.end(); ++it)
if ((*it)->id == id) { records_.erase(it); return true; }
return false;
}
Record* Find(int id) {
for (auto& p : records_) if (p->id == id) return p.get();
return nullptr;
}
void SortByScoreDesc() {
records_.sort([](auto& a, auto& b) { return a->score > b->score; });
}
void DisplayAll() { for (auto& p : records_) Print(p.get()); }
};
優缺點
| 優點 | 缺點 |
|---|
| 變長記錄 (std::string) 自然支援 | 啟動/關閉需全量讀寫，大檔案慢 |
| 增刪極快 (list O(1) / vector 尾部 O(1)) | 記憶體佔用 = 檔案大小 + 指標開銷 |
| 支援複雜查詢、排序、索引建立 | 非持久化：崩潰會丟失未存資料 |
進階混合方案：B+ 樹 / LSM Tree / mmap
| 方案 | 核心思想 | 適用場景 |
|---|
| 固定長度 + 空閒鏈表 | 刪除記錄加入空閒列表，新增優先復用 | 高頻增刪、固定結構 |
記憶體映射 mmap / MapViewOfFile | 檔案直接映射至虛擬記憶體，指標即位移 | 大檔案、隨機存取、跨進程共享 |
| B+ 樹索引 (SQLite, LevelDB) | 鍵值分離，葉節點鏈表支援範圍查詢 | 通用嵌入式資料庫 |
| LSM Tree (RocksDB, Cassandra) | 寫入優先進 MemTable，定期合併 SSTable | 寫入密集、日誌結構 |
選型決策樹
記錄長度固定嗎？
├─ 是 → 記錄數 < 10萬 且 增刪少？ → 法一 (固定定位)
│ 增刪頻繁？ → 固定長度 + 空閒鏈表 / mmap
└─ 否 (變長) → 檔案 < 50MB 且 可容忍啟動延遲？ → 法二 (記憶體鏈表)
大檔案/高併發/需持久化？ → SQLite / LevelDB / RocksDB
理解「固定定位 O(1) 空間換時間」與「記憶體重組 時間換空間/彈性」的權衡，是設計高效儲存引擎的關鍵。本文兩個範例專案展示最基礎的兩種模式，實務中請根據資料特徵、存取模式、一致性要求選擇或組合進階方案。完整原始碼 (VC6/VS2005、錯誤處理、單元測試) 請參考文章附件。
