聚簇和非聚簇索引/Btree和B+tree

目录

1、聚簇（聚集）索引

（1）特点

（2）优点

（3）缺点

2、二级索引（辅助索引、非聚簇索引）

3、Btree（平衡多路查找树）

4、B+tree

5、MySQL为什么不用红黑树而是用B+tree

（1）磁盘访问效率：

（2）数据组织：

（3）高度平衡：

（4）空间利用率：

（5）并发控制：

6、Btree和B+tree的区别

（1）数据存储位置

（2）节点结构

（3）搜索性能

（4）插入和删除操作

（5）应用场景

---

1、聚簇（聚集）索引

（1）特点

1、使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：

• 页内的记录是按照主键的大小顺序排成一个单向链表。
• 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
• 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

2、 B+树的叶子节点存储的是完整的用户记录。

• 所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。 

（2）优点

• 数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快。
• 聚簇索引对于主键的排序查找和范围查找速度非常快。
• 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的io操作。

（3）缺点

• 插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键。
• 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
• 二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据。

2、二级索引（辅助索引、非聚簇索引）

        回表以某列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根某列的值查找到完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程称为回表 。也就是根据某列的值查询一条完整的用户记录需要使用到2棵B+树。

3、Btree（平衡多路查找树）

        B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组(key,data]，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的教据。对于不同的记录，key值互不相同。

4、B+tree

        所有的叶子结点中包含了全部关键字的信息，非叶子节点只存储键值信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接，所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大(或最小)关键字。(而B树的非终节点也包含需要查找的 有效信息) 。所有叶子节点之间都有一个链指针。数据记录都存放在叶子节点中。

5、MySQL为什么不用红黑树而是用B+tree

（1）磁盘访问效率：

        数据库系统通常需要处理大量的数据，这些数据往往存储在磁盘上。磁盘访问的代价远高于内存访问，因此优化磁盘访问效率至关重要。B+树的设计特别适合磁盘存储， 其节点可以容纳更多的键值对，减少了磁盘I/O次数。

（2）数据组织：

        B+树将所有数据记录存储在叶子节点上，而叶子节点只包含键值和指向其他节点的指针。这种结构使得范围查询和顺序访问更加高效，因为数据记录在叶子节点上连续存 储，便于磁盘的顺序读取。

（3）高度平衡：

        B+树的高度通常较低，因为每个节点可以包含更多的子节点。这意味着从根节点到叶子节点的距离较短，查询效率更高。红黑树虽然也是平衡树，但在插入和删除操作中可能需要进行较多的结构调整，以保持平衡。

（4）空间利用率：

        B+树的空间利用率更高。由于非叶子节点不存储数据记录，节点的空间可以被更充分地利用，减少了空间浪费。

（5）并发控制：

        在数据库系统中，并发访问和锁机制是非常重要的。B+树的结构使得它可以更好地支持并发操作，尤其是在进行范围查询时，可以更容易地实现锁的粒度控制。

        综上所述，B+树在磁盘存储、数据组织、查询效率、空间利用率和并发控制等方面都更适合用于数据库索引，因此MySQL选择了B+树作为其索引数据结构。

6、Btree和B+tree的区别

（1）数据存储位置

• B树: 数据可以存储在非叶子节点和叶子节点中。每个节点包含一组键值对，这些键值对按顺序排列。
• B+树: 所有数据记录都存储在叶子节点中。非叶子节点仅包含键值，用于指导搜索路径。

（2）节点结构

• B树: 每个节点包含多个键值对和多个子节点指针。节点内的键值对和子节点指针数量之间存在一定的关系，以保持平衡。
• B+树: 每个非叶子节点包含多个键值和相同数量的子节点指针。叶子节点除了包含数据记录外，还包含指向相邻叶子节点的指针，形成一个链表。

（3）搜索性能

• B树: 搜索操作可能需要访问非叶子节点，搜索路径上的每个节点都需要比较和跳转。
• B+树: 搜索操作只需访问叶子节点。由于叶子节点形成一个链表，搜索过程中可以快速遍历所有键值。

（4）插入和删除操作

• B树: 插入和删除操作可能导致节点分裂或合并，不能维护树的平衡。
• B+树: 插入和删除操作仅影响叶子节点，非叶子节点仅需更新键值和指针信息。

（5）应用场景

• B树: 适用于需要快速访问中间节点数据的场景，如文件系统中的目录结构。
• B+树: 适用于需要频繁搜索、插入和删除操作的场景，如数据库索引。由于所有数据都在叶子节点，B+树在范围查询和排序方面更具优势。