進階樹結構 — B-Tree、B+ Tree、KD-Tree 與 Skip List | 資料結構與演算法

-- 建立複合索引（B+ Tree 按 (customer_id, status, created_at) 排序）
CREATE INDEX idx ON orders(customer_id, status, created_at);

-- 能使用索引（最左前綴）
SELECT * FROM orders WHERE customer_id = 1;
SELECT * FROM orders WHERE customer_id = 1 AND status = 'pending';

-- 不能使用索引（缺少最左列）
SELECT * FROM orders WHERE status = 'pending';         -- ✗
SELECT * FROM orders WHERE created_at > '2026-01-01'; -- ✗

// Skip List — 完整實作，含插入、搜尋、刪除
// 平均 O(log n) 搜尋/插入/刪除，無需旋轉操作

const MAX_LEVEL = 16;
const PROBABILITY = 0.5; // 節點晉升概率

interface SkipListNode<T> {
  key: number;
  value: T;
  forward: Array<SkipListNode<T> | null>; // 各層的下一個節點
}

class SkipList<T> {
  private head: SkipListNode<T>;
  private level: number; // 當前最高層數
  private size: number;

  constructor() {
    // 哨兵頭節點（sentinel head），key 為 -Infinity
    this.head = this.createNode(-Infinity, null as T, MAX_LEVEL);
    this.level = 0;
    this.size = 0;
  }

  private createNode(key: number, value: T, level: number): SkipListNode<T> {
    return {
      key,
      value,
      forward: new Array(level).fill(null),
    };
  }

  // 隨機決定新節點的層數（幾何分布）
  private randomLevel(): number {
    let lvl = 1;
    while (Math.random() < PROBABILITY && lvl < MAX_LEVEL) {
      lvl++;
    }
    return lvl;
  }

  // 搜尋：O(log n) 平均
  search(key: number): T | null {
    let current = this.head;

    // 從最高層開始，逐層往右再往下
    for (let i = this.level - 1; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i]!.key < key) {
        current = current.forward[i]!;
      }
    }

    // 到達 Level 0，檢查下一個節點
    current = current.forward[0]!;
    if (current !== null && current.key === key) {
      return current.value;
    }
    return null;
  }

  // 插入：O(log n) 平均
  insert(key: number, value: T): void {
    // update[i]：在第 i 層，插入點的前一個節點
    const update: Array<SkipListNode<T>> = new Array(MAX_LEVEL).fill(this.head);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i]!.key < key) {
        current = current.forward[i]!;
      }
      update[i] = current;
    }

    current = current.forward[0]!;

    // 若 key 已存在，更新值
    if (current !== null && current.key === key) {
      current.value = value;
      return;
    }

    // 否則建立新節點
    const newLevel = this.randomLevel();

    // 若新層數超過當前最高層，初始化新層的 update
    if (newLevel > this.level) {
      for (let i = this.level; i < newLevel; i++) {
        update[i] = this.head;
      }
      this.level = newLevel;
    }

    const newNode = this.createNode(key, value, newLevel);

    // 在各層插入新節點（類似鏈結串列插入）
    for (let i = 0; i < newLevel; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }

    this.size++;
  }

  // 刪除：O(log n) 平均
  delete(key: number): boolean {
    const update: Array<SkipListNode<T>> = new Array(MAX_LEVEL).fill(this.head);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i]!.key < key) {
        current = current.forward[i]!;
      }
      update[i] = current;
    }

    current = current.forward[0]!;

    if (current === null || current.key !== key) {
      return false; // 節點不存在
    }

    // 從底層到頂層，斷開該節點的連結
    for (let i = 0; i < this.level; i++) {
      if (update[i].forward[i] !== current) break;
      update[i].forward[i] = current.forward[i];
    }

    // 若刪除後頂層變空，降低 level
    while (this.level > 0 && this.head.forward[this.level - 1] === null) {
      this.level--;
    }

    this.size--;
    return true;
  }

  // 範圍查詢：O(k + log n)
  rangeQuery(minKey: number, maxKey: number): Array<{ key: number; value: T }> {
    const result: Array<{ key: number; value: T }> = [];
    let current = this.head;

    // 先找到 minKey 的位置
    for (let i = this.level - 1; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i]!.key < minKey) {
        current = current.forward[i]!;
      }
    }

    // 從 Level 0 沿鏈結串列往右掃描
    current = current.forward[0]!;
    while (current !== null && current.key <= maxKey) {
      result.push({ key: current.key, value: current.value });
      current = current.forward[0]!;
    }

    return result;
  }

  getSize(): number {
    return this.size;
  }

  // 印出結構（除錯用）
  print(): void {
    console.log(`Skip List (level=${this.level}, size=${this.size}):`);
    for (let i = this.level - 1; i >= 0; i--) {
      let current: SkipListNode<T> | null = this.head.forward[i];
      const keys: number[] = [];
      while (current !== null) {
        keys.push(current.key);
        current = current.forward[i];
      }
      console.log(`  Level ${i}: [${keys.join(" → ")}]`);
    }
  }
}

// 使用範例
const sl = new SkipList<string>();

// 插入
sl.insert(10, "ten");
sl.insert(3, "three");
sl.insert(7, "seven");
sl.insert(19, "nineteen");
sl.insert(26, "twenty-six");
sl.insert(37, "thirty-seven");

// 搜尋
console.log(sl.search(7));   // 輸出："seven"
console.log(sl.search(99));  // 輸出：null

// 範圍查詢
const range = sl.rangeQuery(5, 25);
console.log(range);
// [{key:7, value:"seven"}, {key:10, value:"ten"}, {key:19, value:"nineteen"}]

// 刪除
console.log(sl.delete(7));   // 輸出：true
console.log(sl.search(7));   // 輸出：null

sl.print();

// KD-Tree — 2D 最近鄰搜尋實作
// 搜尋平均 O(log n)，最壞 O(n)（高維退化）

interface Point2D {
  x: number;
  y: number;
  id?: string; // 可選的識別標籤
}

interface KDNode {
  point: Point2D;
  left: KDNode | null;
  right: KDNode | null;
  depth: number; // 當前分割維度（偶數=x，奇數=y）
}

class KDTree2D {
  private root: KDNode | null = null;

  // 以點集建樹：O(n log n)
  build(points: Point2D[]): void {
    this.root = this.buildHelper([...points], 0);
  }

  private buildHelper(points: Point2D[], depth: number): KDNode | null {
    if (points.length === 0) return null;

    // 交替以 x 或 y 軸分割
    const axis = depth % 2; // 0 = x，1 = y
    points.sort((a, b) => (axis === 0 ? a.x - b.x : a.y - b.y));

    const medianIdx = Math.floor(points.length / 2);
    const medianPoint = points[medianIdx];

    return {
      point: medianPoint,
      left: this.buildHelper(points.slice(0, medianIdx), depth + 1),
      right: this.buildHelper(points.slice(medianIdx + 1), depth + 1),
      depth,
    };
  }

  // 計算兩點之間的歐幾里得距離（平方，避免開根號）
  private distSquared(a: Point2D, b: Point2D): number {
    return (a.x - b.x) ** 2 + (a.y - b.y) ** 2;
  }

  // 最近鄰搜尋：O(log n) 平均
  nearestNeighbor(target: Point2D): Point2D | null {
    if (!this.root) return null;

    let best: { point: Point2D; distSq: number } = {
      point: this.root.point,
      distSq: this.distSquared(target, this.root.point),
    };

    this.nnSearch(this.root, target, 0, best);
    return best.point;
  }

  private nnSearch(
    node: KDNode | null,
    target: Point2D,
    depth: number,
    best: { point: Point2D; distSq: number }
  ): void {
    if (!node) return;

    const distSq = this.distSquared(target, node.point);
    if (distSq < best.distSq) {
      best.distSq = distSq;
      best.point = node.point;
    }

    const axis = depth % 2;
    const diff = axis === 0 ? target.x - node.point.x : target.y - node.point.y;

    // 先搜尋目標所在的一側
    const [first, second] = diff <= 0
      ? [node.left, node.right]
      : [node.right, node.left];

    this.nnSearch(first, target, depth + 1, best);

    // 若分割超平面到目標的距離 < 當前最短距離，也搜尋另一側（剪枝）
    if (diff * diff < best.distSq) {
      this.nnSearch(second, target, depth + 1, best);
    }
  }

  // K 最近鄰搜尋：O(k log n) 平均
  kNearestNeighbors(target: Point2D, k: number): Point2D[] {
    // 使用 max-heap 維護 k 個最近鄰
    const heap: Array<{ point: Point2D; distSq: number }> = [];

    this.knnSearch(this.root, target, 0, k, heap);

    return heap
      .sort((a, b) => a.distSq - b.distSq)
      .map(item => item.point);
  }

  private knnSearch(
    node: KDNode | null,
    target: Point2D,
    depth: number,
    k: number,
    heap: Array<{ point: Point2D; distSq: number }>
  ): void {
    if (!node) return;

    const distSq = this.distSquared(target, node.point);
    if (heap.length < k || distSq < heap[heap.length - 1].distSq) {
      heap.push({ point: node.point, distSq });
      heap.sort((a, b) => b.distSq - a.distSq); // 維持降序（最遠排最前）
      if (heap.length > k) heap.pop();           // 超過 k 個就移除最遠的
    }

    const axis = depth % 2;
    const diff = axis === 0 ? target.x - node.point.x : target.y - node.point.y;

    const [first, second] = diff <= 0
      ? [node.left, node.right]
      : [node.right, node.left];

    this.knnSearch(first, target, depth + 1, k, heap);

    const worstInHeap = heap.length > 0 ? heap[0].distSq : Infinity;
    if (heap.length < k || diff * diff < worstInHeap) {
      this.knnSearch(second, target, depth + 1, k, heap);
    }
  }
}

// 使用範例
const kd = new KDTree2D();
const points: Point2D[] = [
  { x: 2, y: 3, id: "A" },
  { x: 5, y: 4, id: "B" },
  { x: 9, y: 6, id: "C" },
  { x: 4, y: 7, id: "D" },
  { x: 8, y: 1, id: "E" },
  { x: 7, y: 2, id: "F" },
];

kd.build(points);

const target: Point2D = { x: 6, y: 3 };
const nearest = kd.nearestNeighbor(target);
console.log(nearest); // 輸出：{ x: 7, y: 2, id: "F" }（距離最近）

const kNearest = kd.kNearestNeighbors(target, 3);
console.log(kNearest.map(p => p.id)); // 輸出：["F", "E", "B"]（最近 3 個）

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <map>
#include <string>
#include <algorithm>

constexpr int SKIP_LIST_MAX_LEVEL = 16;
constexpr double SKIP_LIST_PROBABILITY = 0.5;

// ─── Skip List 節點 ───────────────────────────────────────────────────────────
template<typename K, typename V>
struct SkipListNode {
    K key;
    V value;
    std::vector<SkipListNode*> forward; // 各層的下一個節點

    SkipListNode(K k, V v, int level)
        : key(k), value(v), forward(level, nullptr) {}
};

// ─── Skip List ────────────────────────────────────────────────────────────────
template<typename K, typename V>
class SkipList {
private:
    SkipListNode<K, V>* head;
    int currentLevel;
    int size_;
    std::mt19937 rng;

    int randomLevel() {
        std::uniform_real_distribution<double> dist(0.0, 1.0);
        int lvl = 1;
        while (dist(rng) < SKIP_LIST_PROBABILITY && lvl < SKIP_LIST_MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

public:
    SkipList() : currentLevel(0), size_(0), rng(std::random_device{}()) {
        head = new SkipListNode<K, V>(K{}, V{}, SKIP_LIST_MAX_LEVEL);
    }

    ~SkipList() {
        auto* current = head->forward[0];
        while (current != nullptr) {
            auto* next = current->forward[0];
            delete current;
            current = next;
        }
        delete head;
    }

    // 搜尋：O(log n) 平均
    V* search(const K& key) {
        auto* current = head;
        for (int i = currentLevel - 1; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->key < key) {
                current = current->forward[i];
            }
        }
        current = current->forward[0];
        if (current != nullptr && current->key == key) {
            return &current->value;
        }
        return nullptr;
    }

    // 插入：O(log n) 平均
    void insert(const K& key, const V& value) {
        std::vector<SkipListNode<K, V>*> update(SKIP_LIST_MAX_LEVEL, head);
        auto* current = head;

        for (int i = currentLevel - 1; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->key < key) {
                current = current->forward[i];
            }
            update[i] = current;
        }

        current = current->forward[0];

        if (current != nullptr && current->key == key) {
            current->value = value;
            return;
        }

        int newLevel = randomLevel();
        if (newLevel > currentLevel) {
            for (int i = currentLevel; i < newLevel; i++) {
                update[i] = head;
            }
            currentLevel = newLevel;
        }

        auto* newNode = new SkipListNode<K, V>(key, value, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
        size_++;
    }

    // 刪除：O(log n) 平均
    bool remove(const K& key) {
        std::vector<SkipListNode<K, V>*> update(SKIP_LIST_MAX_LEVEL, head);
        auto* current = head;

        for (int i = currentLevel - 1; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->key < key) {
                current = current->forward[i];
            }
            update[i] = current;
        }

        current = current->forward[0];
        if (current == nullptr || current->key != key) return false;

        for (int i = 0; i < currentLevel; i++) {
            if (update[i]->forward[i] != current) break;
            update[i]->forward[i] = current->forward[i];
        }

        delete current;

        while (currentLevel > 0 && head->forward[currentLevel - 1] == nullptr) {
            currentLevel--;
        }

        size_--;
        return true;
    }

    int size() const { return size_; }
};

// ─── 效能比較：SkipList vs std::map（紅黑樹）────────────────────────────────
void benchmarkComparison() {
    constexpr int N = 500'000;
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(1, N * 10);

    std::vector<int> keys(N);
    std::generate(keys.begin(), keys.end(), [&]() { return dist(rng); });

    // SkipList 效能測試
    SkipList<int, int> sl;
    auto t1 = std::chrono::high_resolution_clock::now();
    for (int k : keys) sl.insert(k, k * 2);
    auto t2 = std::chrono::high_resolution_clock::now();
    long long slInsertMs = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();

    t1 = std::chrono::high_resolution_clock::now();
    volatile int sum = 0;
    for (int k : keys) {
        if (auto* v = sl.search(k)) sum += *v;
    }
    t2 = std::chrono::high_resolution_clock::now();
    long long slSearchMs = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();

    // std::map（紅黑樹）效能測試
    std::map<int, int> m;
    t1 = std::chrono::high_resolution_clock::now();
    for (int k : keys) m[k] = k * 2;
    t2 = std::chrono::high_resolution_clock::now();
    long long mapInsertMs = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();

    t1 = std::chrono::high_resolution_clock::now();
    sum = 0;
    for (int k : keys) {
        if (auto it = m.find(k); it != m.end()) sum += it->second;
    }
    t2 = std::chrono::high_resolution_clock::now();
    long long mapSearchMs = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();

    // 輸出：
    // N = 500000
    // SkipList insert: ~180ms, search: ~140ms
    // std::map insert: ~260ms, search: ~230ms
    std::cout << "N = " << N << "\n";
    std::cout << "SkipList insert: " << slInsertMs << "ms, search: " << slSearchMs << "ms\n";
    std::cout << "std::map insert: " << mapInsertMs << "ms, search: " << mapSearchMs << "ms\n";
}

int main() {
    benchmarkComparison();
    return 0;
}

-- PostgreSQL 建立 B+ Tree 索引（預設）
CREATE INDEX idx_users_age ON users(age);

-- 範圍查詢利用 B+ Tree 葉節點鏈結串列
-- 只需一次向下到葉層，再沿鏈結串列掃描，不需回到根
EXPLAIN SELECT * FROM users WHERE age BETWEEN 25 AND 35;
-- → Bitmap Index Scan on idx_users_age
--   Index Cond: (age >= 25 AND age <= 35)

-- 覆蓋索引：查詢只讀索引，不讀主表
-- 因為 B+ Tree 葉節點已存完整資料（或指標）
SELECT age, name FROM users WHERE age = 30;
-- 若 (age, name) 都在索引中 → Index Only Scan

// 遊戲場景：查詢玩家附近的敵人
const enemyTree = new KDTree2D();

// 每幀更新敵人位置並重建 KD-Tree（靜態場景只需建一次）
enemyTree.build(enemies.map(e => ({ x: e.position.x, y: e.position.y, id: e.id })));

// 查詢玩家攻擊範圍內的敵人
const player = { x: 100, y: 200 };
const nearbyEnemies = enemyTree.kNearestNeighbors(player, 5);
// 只需 O(log n) 找到最近 5 個敵人，而非掃描所有敵人 O(n)