HOME

数据结构

B树

  1. 每个节点可以拥有若干个子节点
    1. 根节点可以拥有[2, m]个子节点
    2. 非叶子结点可以拥有[m/2, m]个子节点
  2. 每个节点可以拥有(0, m]个关键字和指针
  3. 每个节点的关键字k[1],k[2]...k[m - 1]满足以下规律
    1. k[1] < k[2] <...<k[m - 1]
  4. 每个节点的指针p[1],p[2]...p[m]满足如下规律
    1. p[1]指向的子节点的关键字k' < k[1]
    2. p[i]指向的子节点的关键字k[i - 1] < k'[i] < k[i + 1]
    3. p[m]指向的子节点的关键字k'[m] > k[m - 1]
  5. 节点都在一层

B+树

相对于B树，增加了如下规律

  1. 关键字只存在于叶子节点
  2. 叶子结点上存在指向下一个叶子节点的指针

B*树

相对于B+树，增加了如下规律

  1. 每个非叶子节点可以拥有[2/3m, m]个节点
  2. 每个非叶子结点还存储了其兄弟节点的指针
  3. 分裂时，先看兄弟节点是否有空闲，
    1. 有的话放入兄弟节点
    2. 没空的话与兄弟节点分别拿出1/3组成新节点

innodb索引

索引分类

聚簇索引

创建条件：一般是主键索引，当指定主键时，会根据主键建立聚簇索引 当未指定主键时，寻找unique列建立聚簇索引 若没有unique列，则在隐藏列建立聚簇索引 特点：叶子结点上存储整条数据

二级索引

特点：叶子结点上存储关键字数据和聚簇索引指针

索引匹配过程

select * from user where a >= 0 and a <= 1 and b = 2 and c > 1 and c < 10 and d != 4 and e = 1 i_index1(a, b, c) i_index2(e) 数据的匹配一般有如下步骤

  1. index key
    1. index first key

找到where中=、>=、in操作符，以>、!=截止 我们可以找到a>=0，b=2，c > 1

  1. index last key

找到where条件中=、<=、in操作符，以<、!=截止 我们可以找到a<=1，b=2，c<10

  1. index filter

在步骤一中找到的数据，逐条跟i_index2比较，即判断是否e=1 5.6之前不支持，5.6之后有了ICP就支持了

  1. table filter

mysql server层中进行，将筛选出的数据跟最后作比较，及判断是否满足d!=4

常见问题

为什么是最左匹配？

a like 'asdf%'则可以走a相关的索引，a like '%asdf'则走不到，字符串在创建索引时是根据字典序创建的

回表是什么？

根据二级索引进行筛选数据时，需要根据索引上存储的聚簇索引指针回到聚簇索引中去取数据

一颗B+树能存多少数据？

每棵树能存的最大数据量和其层数以及阶树有关 设主键的存储类型所占空间为x，整行数据所占空间为y innodb的最小存储单元为页，每页16k B+树的非叶子结点所占空间为x + 指针所占空间，即（x + 6），那么每页可以存储16k/(x+6)个指针，即这颗B+树最多16k/(x+6)阶 每个指针指向一个数据页，每个数据页能存的数据就是16k/y 故每棵树能存的最大数据量为[(16k/(x + 6))的(层数-1)次方] * 16k/y 接下来我们代入数据 假设主键存储类型为bigint，即x=8，每行数据为1k，B+树的高度为2 (16k/(8 + 6)) * 16 = 1174 16= 18724 当B+树的高度为3 [(16k/(8 + 6))的平方 ] 16 = 1174 16= 21902400 当B+树的高度为4 [(16k/(8 + 6))的三次方 ] 16 = 1174 *16= 200多亿