索引

mysql 中索引的数据结构是 B+ 树，B+ 树是一种自平衡的树数据结构，具有以下特点：

• 所有的值都在叶子节点上，非叶子节点只存储索引。所有节点都会存储数据是 B 树的特征
• 所有的叶子节点都在同一层上。
• 每个节点可以有多个子节点，具体的数量由 B+ 树的阶数决定。
• 每个节点的值是有序的，且每个节点的值都大于等于它的左子节点的值，小于等于它的右子节点的值。
• 每个节点的值都可以通过指针连接到下一个节点，形成一个链表，这样可以提高范围查询的效率。
• B+ 树的高度是 O(log n)，其中 n 是节点的数量，这样可以保证查询的效率。
• B+ 树的插入和删除操作都是 O(log n)，这也是 B+ 树的一个重要特点。
• B+ 树的查询效率是 O(log n)，这也是 B+ 树的一个重要特点。
• B+ 树的范围查询效率是 O(k + log n)，其中 k 是查询的结果集的大小，这也是 B+ 树的一个重要特点。
• B+ 树的空间复杂度是 O(n)，其中 n 是节点的数量，这也是 B+ 树的一个重要特点。

在 MySQL 的 innodb 引擎中分为聚簇索引和非聚簇索引，MyISAM 引擎中只有非聚簇索引。

• 聚簇索引又叫主键索引，是把主键作为索引，数据存储在叶子节点上，非叶子节点存储的是索引值和指向数据的指针。聚簇索引的特点是查询效率高，但是插入和删除效率低，因为需要移动数据。
• 非聚簇索引是把非主键作为索引，数据存储在叶子节点上，同时它也会存储主键的值，非叶子节点存储的是索引值和指向数据的指针。非聚簇索引的特点是查询效率低，但是插入和删除效率高，因为不需要移动数据。

回表

就是当用户查询非主键索引也就是非聚簇索引的时候，查询到了不是该索引的数据，这时候就需要进行回表操作，拿到叶子结点中的主键的值，去到聚簇索引也就是主键索引里查找其他的不是该索引列的值。