切换语言为:繁体

从索引的结构「B+树」角度分析为什么索引匹配按照最左匹配原则

  • 爱糖宝
  • 2024-07-30
  • 2067
  • 0
  • 0

最左匹配原则是B+树索引的一个重要特性,它指的是在使用复合索引(即包含多个列的索引)时,查询条件必须从索引的最左边列开始才能利用索引。下面我们从B+树索引的结构角度来解释为什么会有最左匹配原则。

B+树索引结构

B+树索引是一种广泛使用的索引结构,它具有以下特点:

  • 键值对:

    • B+树的每个节点包含键值对,键是索引列的值,值通常是指向实际数据行的指针。

  • 有序排列:

    • B+树中的键按照排序顺序存储。

  • 叶子节点:

    • 所有的数据行指针都存储在叶子节点中,叶子节点之间通过指针相连,形成一个链表。

  • 非叶子节点:

    • 非叶子节点用于索引的分层结构,帮助快速定位到叶子节点。

最左匹配原则的解释

  1. 索引列顺序:

    • 在复合索引中,索引列的顺序决定了B+树中键的顺序。例如,如果有一个复合索引 (col1, col2, col3),那么B+树中的键就是 (col1, col2, col3) 的值组成的元组。

  2. 索引查找:

    • 当执行查询时,MySQL 会从根节点开始,根据查询条件中的第一个列(即复合索引中最左边的列)的值向下遍历B+树。

    • 如果查询条件从最左边的列开始,MySQL 可以沿着树的路径向下移动,直到找到匹配的键值对。

    • 如果查询条件不从最左边的列开始,MySQL 无法有效地使用索引,因为无法确定从哪个分支开始查找。

  3. 例子:

    • 假设有一个复合索引 (col1, col2, col3),并且执行以下查询:

      SELECT * FROM table_name WHERE col1 = 1 AND col2 = 2 AND col3 = 3;
    • 这个查询从复合索引的最左边开始,因此可以有效地使用索引。

    • 然而,如果执行以下查询:

      SELECT * FROM table_name WHERE col2 = 2 AND col3 = 3;
    • 由于查询条件没有从最左边的列开始,MySQL 无法有效地使用索引 (col1, col2, col3)。

图解说明

假设我们有一个复合索引 (col1, col2, col3),B+树的结构大致如下:

          +----------------+
          |  (1, 1, 1)     |
          +----------------+
                /    \
        +------------+  +------------+
        | (1, 1, 2) |  | (1, 2, 1)  |
        +------------+  +------------+
         /    \       /    \
    +-------+  +-------+  +-------+  +-------+
    | (1, 1, 3)|  | (1, 1, 4)|  | (1, 2, 2)|  | (1, 2, 3)|
    +-------+  +-------+  +-------+  +-------+
  1. 查询 (col1, col2, col3) = (1, 1, 3):

    • 从根节点开始,根据 col1 的值 1 移动到相应的子节点。

    • 在子节点中,根据 col2 的值 1 移动到相应的子节点。

    • 在叶子节点中,根据 col3 的值 3 查找匹配的行。

  2. 查询 (col2, col3) = (1, 3):

    • 由于没有从最左边的列开始,MySQL 无法有效地使用索引,只能进行全表扫描。

结论

最左匹配原则是B+树索引结构的一个自然结果。在复合索引中,查询条件必须从索引的最左边列开始才能利用索引。这是因为在B+树中,索引键的排序依赖于最左边的列,而索引查找是从根节点开始,沿着树的路径向下移动,直到找到匹配的键值对。如果查询条件不从最左边的列开始,MySQL 无法确定从哪个分支开始查找,因此无法有效利用索引。


源自:ai

0条评论

您的电子邮件等信息不会被公开,以下所有项均必填

OK! You can skip this field.