InnoDB存儲引擎核心數據結構深度解析：Vector、List、Hash、Queue

InnoDB源碼級核心數據結構剖析

基於MySQL 5.6/5.7源碼分析，InnoDB為了高併發、高可靠性，自行實現了不依賴STL的核心數據結構，統一管理內存分配與線程同步。

1. 動態數組

特點：類似C++ vector，支援自定義內存分配器（Heap/OS malloc）。

struct ib_alloc_t {
  ib_mem_alloc_t  mem_malloc;   // 分配函數指針
  ib_mem_free_t   mem_free;     // 釋放函數指針
  ib_mem_resize_t mem_resize;   // 重分配函數指針
  void*           arg;          // 堆句柄，NULL表示用系統malloc
};

• 內建qsort快速排序
• 內存結構：連續數組 + 容量/大小元數據
• 擴容策略：通常2倍增長

2. 雙向鏈表

標準實現：ib_list_node_t含prev/next指針。

• 創建方式決定內存來源：ib_list_create_heap（Heap）vs ib_list_create（malloc）
• 節點內存統一從Heap分配
• 適用場景：LRU列表、Flush列表、事務鏈表

3. 線程安全FIFO隊列

struct ib_wqueue_t {
  ib_mutex_t mutex;      // 互斥鎖保護items
  ib_list_t* items;      // 底層用List實現
  os_event_t event;      // 信號量實現生產消費者通知
};

• 多生產者多消費者安全
• mutex保證隊列操作原子性
• event實現高效阻塞等待/喚醒

4. 高性能哈希表

創新點：自定義鏈式桶結構，非傳統List處理碰撞，支援泛型操作宏。

// 核心操作宏
HASH_INSERT, HASH_DELETE, HASH_GET_FIRST, HASH_GET_NEXT
HASH_SEARCH, HASH_SEARCH_ALL, HASH_DELETE_AND_COMPACT
HASH_MIGRATE  // 用於Rehash遷移

並發優化：Cell級鎖粒度

• n_sync_obj必須為2的N次方（如8、16、32）
• 多個Cell共享一把鎖，減少鎖內存開銷
• 支持mutex與rw_lock兩種同步模式

struct hash_table_t {
  enum hash_table_sync_t type;   // 同步類型
  ulint n_cells;                 // 桶數量
  hash_cell_t* array;            // 桶數組
  ulint n_sync_obj;              // 鎖數量（2的冪）
  union {
    ib_mutex_t* mutexes;
    rw_lock_t* rw_locks;
  } sync_obj;
  mem_heap_t** heaps;            // 每個鎖對應一個Heap
  mem_heap_t* heap;              // 表級Heap
  ulint magic_n;                 // 魔數校驗
};

5. 設計哲學總結

MySQL 5.7+ 開始大量引入Boost/STL，但在核心存儲引擎路徑上，自研數據結構仍佔主導，這是InnoDB能支撐極高併發的基石。

1. 上一篇文章： MySQL存儲過程完整教程：變量、流程控制、參數傳遞與實戰案例
2. 下一篇文章： MySQL SQL優化實戰：統計分類計數從1.34秒降至0.78秒的兩種寫法對比

MySQL 綜合教學

MariaDB SELECT 語句執行流程與子句解析順序深度解析

MariaDB/MySQL 查詢處理管線：從解析器到存儲引擎

Windows下MySQL 5.1/5.7下載安裝配置與圖形化工具完整教程

Windows下MySQL下載安裝配置與圖形化工具完整教程

Digg 從 MySQL 遷移至 Cassandra NoSQL 架構的技術考量

前言 繼 Twitter 之後，社交新聞網站 Digg 宣佈

MySQL INNER JOIN ON 核心語法與實戰避坑指南

核心語法 SELECT t1.col1, t2.col2 F