檔案系統 File System - paulip114/blog GitHub Wiki

適用於檔案系統的資料結構

🌳 N-ary Tree 概念

• 每個節點可以有 0 到 N 個子節點。

• 非常適合表現像：

  • 檔案系統（每個資料夾可以有很多子資料夾/檔案）

  • 組織圖

  • 分類樹（像是產品分類、物種分類）

  • 範例（檔案系統）：

Root
├── Documents
│   ├── Work
│   └── Personal
├── Downloads
├── Pictures
│   ├── Vacation
│   └── Family

這種結構就是典型的 N-ary Tree（這邊 N 不固定）

太好了！來，我幫你用 TypeScript 寫一個簡單的 N-ary Tree 結構，模擬一個簡單的檔案系統。這個範例會包括：

• 節點類別（FileNode）
• 加入子節點的方法（addChild）
• 遍歷顯示整棵樹的方法（printTree）

---

📁 N-ary Tree 範例：模擬檔案系統（TypeScript）

// 節點類別，代表檔案或資料夾
class FileNode {
  name: string;
  isFolder: boolean;
  children: FileNode[] = [];

  constructor(name: string, isFolder: boolean = true) {
    this.name = name;
    this.isFolder = isFolder;
  }

  // 加入子節點
  addChild(child: FileNode): void {
    if (!this.isFolder) {
      throw new Error("Cannot add child to a file.");
    }
    this.children.push(child);
  }

  // 遞迴印出整棵樹
  printTree(indent: string = ""): void {
    console.log(`${indent}${this.isFolder ? "📁" : "📄"} ${this.name}`);
    for (const child of this.children) {
      child.printTree(indent + "  ");
    }
  }
}

🚀 使用範例

// 建立 root 資料夾
const root = new FileNode("root");

// 建立資料夾和檔案
const documents = new FileNode("Documents");
const pictures = new FileNode("Pictures");
const resume = new FileNode("resume.pdf", false);
const photo = new FileNode("vacation.jpg", false);

// 建立樹狀結構
root.addChild(documents);
root.addChild(pictures);
documents.addChild(resume);
pictures.addChild(photo);

// 印出整棵樹
root.printTree();

🖨️ 輸出結果

📁 root
  📁 Documents
    📄 resume.pdf
  📁 Pictures
    📄 vacation.jpg

這樣你就有了一個簡單的 N-ary Tree 結構，用來模擬檔案系統。

---

用 N-ary tree 還是 B+ tree 比較好？

這取決於檔案系統的規模、用途、效能需求。
以下來分析一下 N-ary Tree 和 B+ Tree 的比較

🌳 一、N-ary Tree 是什麼？

• 每個節點最多有 N 個子節點（N 可以是任意數，不固定）
• 結構簡單、靈活
• 適合用來表示階層型資料（如：檔案總管、目錄結構）

✅ 優點：

• 結構直覺，非常適合開發 UI（例如樹狀選單）
• 加入 / 移除節點簡單
• 不需要排序的話操作效率尚可

❌ 缺點：

• 查找節點效率低：O(n)（因為要逐個比對）
• 沒有自動排序或快速搜尋機制

🌲 二、B+ Tree 是什麼？

B+ Tree 是 B-Tree 的進階版本，廣泛應用於資料庫和檔案系統（像是 NTFS、ext4、HFS+、SQLite）

• 每個節點可包含大量鍵（比 Binary Tree 多很多）
• 所有值（檔案）只存在葉節點
• 葉節點之間會用 linked list 串起來（方便範圍查詢）

✅ 優點：

• 高效率搜尋、插入、刪除（O(log n)）
• 天生支援排序與範圍查詢
• 適合大量資料（上萬筆以上）

❌ 缺點：

• 結構複雜，實作成本較高
• 不如 N-ary Tree 那麼直觀（對開發 UI 或操作較麻煩）

🧠 什麼時候選哪一個？

需求 / 條件	建議用法
資料量小、結構簡單	✅ N-ary Tree
儲存資料是階層結構（檔案總管 UI）	✅ N-ary Tree
需要快速查找、排序、大規模資料處理	✅ B+ Tree
建立檔案系統的底層儲存結構	✅ B+ Tree
檔案數量達數千以上、查詢效率很重要	✅ B+ Tree
UI、顯示邏輯層結構為主	✅ N-ary Tree

🧩 綜合建議（分層設計）

實務上會這樣分層設計系統（也建議你這樣做）：

🔼 上層（UI、邏輯層）→ N-ary Tree

• 顯示目錄結構
• 拖拉檔案、展開節點
• 使用者互動方便直觀

🔽 底層（儲存 / 檢索引擎）→ B+ Tree

• 實作目錄 / 檔案名稱的高效查找
• 範圍搜尋、排序、比對名稱

🧪 TypeScript 實作建議：

功能	資料結構
檔案 UI 樹狀結構	N-ary Tree
快速找出某路徑 / 檔名	Map + B+ Tree（或 Trie）

---

之前的做法

用 ParentId 作爲連接