目录

一、索引的常见数据结构
二、InnoDB的索引模型
三、索引的维护
四、名词与相关概念解释

一、索引的常见数据结构

• 哈希表：
  以键值对存储数据的结构，缺点会发生hash突出，后面跟着的链表和数组，使得哈希表结构适用于等值查询的场景。

• 二叉树：
  二叉树是搜索效率最高的，时间复杂度是 O(log(N))，为了维持 O(log(N)) 的查询复杂度，得保持这颗树是一颗平衡二叉树。

• B+树：
  但索引不止存在内存中，还要写到磁盘上。二叉树的深度比较深，读取磁盘需要时间，所有引出了N叉树降低磁盘访问开销。

返回顶部目录

二、InnoDB的索引模型

• InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的

• 每一个索引在 InnoDB 里面对应一棵 B+ 树

• 假设，我们有一个主键列为 ID 的表，表中有字段 value，并且在 value上有索引。

  mysql> create table T
  (id int primary key,
   value int not null, 
   name varchar(16),
   index (value)
   )engine=InnoDB;
  

  表中 R1~R5 的 (ID,value) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。
  

  • 根据叶子节点的内容，索引类型分为主键索引和非主键索引。

  • 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

  • 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

  • 例子：主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；如果语句是 select * from T where value=5，即普通索引查询方式，则需要先搜索 value 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

返回顶部目录

三、索引的维护

• 在上面的表中，如果新插入的行ID值为400,需要逻辑上挪动后面的数据，空出位置。
• 如果那个数据页数据满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
• 基于上面的问题，我们在很多建表规范中，都有这样的描述，建表需要一定要有自增主键。
  • 每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
  • 而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
• 由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号等做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
• 业务字段直接做主键的（典型的kv场景）,可以避免每次查询需要回表搜索两棵树：
  • 只有一个索引；
  • 该索引必须是唯一索引。

返回顶部目录

名词与相关概念解释

• 为什么数据库存储使用b+树 而不是二叉树？

  • 因为二叉树树高过高，每次查询都需要访问过多节点，即访问数据块过多，而从磁盘随机读取数据块过于耗时。
  • 一页就是B-tree上的一个节点,因为根节点总是在内存,所以查找一个值最多进行树高h-1次磁盘io就能找到。
  • 虽然平衡二叉树时间复杂度低，但树深度可能较深，每一个层级的访问都伴随着磁盘的访问。

• 为什么 “N 叉”树中的“N”取决于数据块的大小？

  • 一个数据块假如有500 字节，一个子节点的索引地址大小是10个字节，那么这个节点就可以存储50个孩子节点的索引，这个树就是50叉树，所以 N取决于数据块的大小。

• 为什么 InnoDB整数字段索引的b+树最大能维持大约1200叉树

  • MySql默认一个节点的长度为16K，一个整数（bigint）字段索引的长度为 8B,另外每个索引还跟着6B的指向其子树的指针；所以16K/14B ≈ 1170

• 比较新的数据结构

  • redis 中使用到跳表，hbase memstore 和flink中的rocksdb使用到LSM树

• 关于 InnoDB 的表结构：

  • 1.在 InnoDB 中，每一张表其实就是多个 B+ 树，即一个主键索引树和多个非主键索引树。 2.执行查询的效率，使用主键索引 > 使用非主键索引 > 不使用索引。 3.如果不使用索引进行查询，则从主索引 B+ 树的叶子节点进行遍历。

• 回表：

  • 主键索引的b+树的叶子节点存储的是具体的行数据，非叶子节点存储的是主键的值。叶子节点之间通过链表连接 非主键索引的叶子节点存储的是主键的值，所以通过非主键索引查询数据时，先找到主键，再去主键索引上根据主键找到具体的行数据

• 根据具体需求选择合适的结构

  • 二叉树也会畸变成单链表，所以才有了AVL树通过旋转的方式来维持树的平衡，但后来发现大量的旋转实在是性能不好，所以有了红黑树。都是二叉树，只是约束条件不一样。没有最好的方法只有更适合的方法，要维持某一方面的优势需要牺牲另一方面的优势，就看如何选择了。