B树与B+树：

B树：

  • “B-树”即“B树”，中间是横杠，而不是减号
  • Balance Tree：多路平衡查找树
  • B树的所有叶子节点都在同一层，每次插入或删除元素会重新平衡

B+树：

  • 有两种类型的几点：内部节点（索引节点）和叶子节点
    • 内部节点：非叶子节点，不存储数据，只存储索引
    • 叶子节点：存储数据
  • 相邻的叶子节点之间有指针相连，叶子节点从左到右是自小而大的
  • 父节点存有右孩子的第一个元素的索引

B+树优势：

  • 单一节点存储的元素更多，使得查询的 IO 次数更少
  • 所有的查询都要到叶子节点，查询性能是稳定的。而 B树不同 key 的查询时间可能不同
  • 所有的叶子节点形成一个有序链表，更加便于查找

InnoDB：

底层存储结构：B+树

  • 每个节点对应 InnoDB 的一个 Page，Page 的大小固定为 16K（TODO Page?）
  • 非叶子节点只有 Key，叶子节点包含 Key 和行数据

image.png
非主键索引：B+树，叶子节点存储索引主键

image.png

索引类型：

  • 聚簇索引：叶子节点存储了行数据，比如主键索引
    • 一个表仅有一个聚簇索引
    • 默认使用主键
    • 若没有定义主键，InnoDB 会选择一个唯一且非空的索引代替
    • 若没有这样的索引，InnoDB 会隐式定义一个主键来作为聚簇索引
  • 非聚簇索引（二级索引）：叶子节点只存储了主键，需要根据主键再查询一次聚簇索引（回表）

InnoDB 的优点

  • 支持事务
  • 支持外键
  • 支持表、行（默认）级锁
  • 是聚簇索引，使用 B+树作为索引结构
  • 不保存表的具体行数，select count(*) from table 时需要全表扫描
  • 表必须有主键，没有的话会自动生成一个
  • 不支持哈希索引

MyISAM

  • 不支持事务
  • 不支持外键
  • 只支持到表锁
  • 是非聚簇索引，也是使用 B+树作为索引结构。索引和数据文件是分离的
  • 保存行数，速度快
  • 表可以没有主键
  • 不支持哈希索引

Memory：

  • 使用内存来创建表，快
  • 哈希索引

image.png