这篇文章只打算介绍InnoDB以B+ Tree为基础的索引模型，并不过多的从源码细节上分析
InnoDB的索引全貌大致是（引用自B+Tree index structures in InnoDB）：

其中（只能保证大致上正确）：

  • 树高度的定义：叶子节点是0，父节点高度是子节点高度+1
  • 每一个Record由Key + Value组成：
    • 中间节点的Value：是一个Pointer（page_no），指向一个下一高度的一个Page（可能是中间节点，可能是叶子节点）
    • 中间节点的Key：是Pointer指向的Page中最小的Key
    • 叶子节点的Value：非主键列
    • 叶子节点的Key：主键列
  • 同一高度的Page连接成“双向链表”，称作Page List
  • 同一Page的Record连接成“单向链表”，称作Record List（按Record的Key升序连接）
  • Infimum（下确界）：一个Page中，Record List的头节点

  • Supremum（上确界）：一个Page中，Record List的尾节点

    查找的实现

    在InnoDB中，对索引的查找是通过三个函数实现：

  • btr_cur_search_to_nth_level：通过对整个B+树的“二分查找”，定位到Page

  • page_cur_search_with_match：在一个Page内“二分查找”（使用Page中的Slot），定位到Record
  • cmp_dtuple_rec_with_match_low：比较定位的Record是否是需要的Record

（未完待续）

参考