我们一起聊聊MySQL 索引的底层逻辑

数据运维 2024-01-03 向阳逐梦 手机阅读

数据结构以及算法

索引的本质其实就是一种数据结构。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找，这种复杂度为 O(n) 的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找、二叉树查找等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

图片图片

1.1 B-Tree

为了描述 B-Tree ，首先定义一条数据记录为一个二元组 [key, data] ， key 为记录的键值，对于不同数据记录， key 是互不相同的；data 为数据记录除 key 外的数据。那么 B-Tree 是满足下列条件的数据结构：

  • d 为大于 1 的一个正整数，称为 B-Tree 的度。
  • h 为一个正整数，称为 B-Tree 的高度。
  • 每个非叶子节点由 n-1 个 key 和 n 个指针组成，其中 dnode); } return BTree_Search(point[i+1]->node); } data = BTree_Search(root, my_key);

    关于 B-Tree 有一系列有趣的性质，例如一个度为 d 的 B-Tree ，设其索引 N 个 key ，则其树高 h 的上限为 log_d((N+1)/2) ，检索一个 key ，其查找节点个数的渐进复杂度为 O(log_dN) 。从这点可以看出， B-Tree 是一个非常有效率的索引数据结构。

    1.2 B+Tree

    B-Tree 有许多变种，其中最常见的是 B+Tree ，例如 MySQL 就普遍使用 B+Tree 实现其索引结构。与 B-Tree 相比， B+Tree 有以下不同点：