Mysql-Day4

1. 什么是b树

B树是一种自平衡的多路搜索树，广泛应用于数据库和文件系统中，用于高效地存储和检索大量有序数据。在MySQL中，B树是InnoDB和MyISAM等存储引擎默认使用的索引结构。

B树的核心特点：

1. 多路搜索：

   • 每个节点可以包含多个键值和多个子节点指针。

   • 例如：一个阶数为 m 的B树，每个节点最多包含 m-1 个键值，最多有 m 个子节点。

2. 平衡性：

   • 所有叶子节点都位于同一层，确保查找、插入和删除操作的时间复杂度为 O(log n)。

   • 插入和删除时会自动进行节点分裂或合并，以保持树的平衡。

3. 磁盘优化：

   • 每个节点的大小通常与磁盘块（block）对齐，减少I/O访问次数。

   • 高度较低，适合大规模数据存储。

4. 支持范围查询：

   • 键值按顺序排列，便于执行 WHERE 条件中的范围查询（如 WHERE id > 100 AND id < 200）。

5. 适用于索引：

   • MySQL使用B树索引来加速数据检索。

   • 支持主键索引、唯一索引、普通索引等多种类型。

B树在MySQL中的应用：

1. 主键索引（Primary Key Index）

• 每张表必须有一个主键，且主键值唯一且非空。

• InnoDB 引擎使用主键构建聚簇索引（Clustered Index），数据按照主键顺序存储。

2. 辅助索引（Secondary Index）

• 非主键索引，指向主键的值。

• 查询时先通过辅助索引找到主键值，再通过主键索引回表查找完整记录。

3. 联合索引（Composite Index）

• 基于多个列建立的复合索引。

• 遵循最左前缀原则（Leftmost Prefix Principle）。

2. b树的根节点是如何分裂出新节点的，1层的b树，根节点分裂出的新节点是不是叶子结点

2. 根节点的分裂过程

(1) 根节点未满时

当根节点还没有达到最大键值数量时，插入新键值不会导致根节点分裂。此时，键值会被直接插入到适当的位置，保持键值的有序性。

(2) 根节点已满时

如果根节点已经满了（即它包含了 m-1 个键值），再插入一个新的键值会导致根节点分裂。这个过程如下：

1. 创建新节点：生成两个新的节点作为原根节点的“兄弟节点”。

2. 中间键值提升：将原根节点的中间键值提取出来，作为新的根节点的唯一键值。

3. 分配子节点：

   • 原根节点的前一半键值保留在原节点中。

   • 后一半键值被移动到新创建的兄弟节点中。

4. 连接新旧节点：

   • 新的根节点的两个子节点分别是原来的根节点和新创建的兄弟节点。

5. 更新树的高度：由于根节点分裂并产生了新的根节点，B树的高度增加了1。

分裂后的根节点是否是叶子节点？

• 如果原来的根节点是非叶子节点，那么分裂后的新根节点仍然是一个非叶子节点，而它的两个子节点（原根节点和新创建的节点）可能仍然是非叶子节点或叶子节点，具体取决于它们的层级。

• 如果原来的根节点是叶子节点（即这是B树的最后一层），那么分裂后的新根节点是一个内部节点，而它的两个子节点仍然是叶子节点。

因此，根节点分裂出的新节点是否是叶子节点，取决于原来的根节点是否是叶子节点。

3. 2层的b树，插入数据时，是插入根节点还是叶子节点

始终是叶子结点

4. 如果叶子节点的数据满了是会向下拆分，还是向上拆分，或者其他什么方式

向上拆分，将中间的节点上溢出。

5. b树中在叶子节点中的数据，可能会移动到根节点中吗？为什么

在 B树中，叶子节点的数据不会移动到根节点，因为数据始终保留在叶子节点中。只有某些键值会在节点分裂过程中被上溢至父节点。

6. b树中的节点除了索引信息外，会携带数据信息吗？为什么这样设计，有什么优缺点

在 B树 中，数据通常只存储在叶子节点中，而内部节点仅作为索引。这种设计是为了提高范围查询效率、减少磁盘 I/O，并保持树的平衡性和一致性。虽然牺牲了一定的插入性能，但换来了更高的查询效率和更好的扩展性，因此被广泛应用于数据库和文件系统中。

7. 什么是b+树，与b树有什么区别

B+ 树是 B 树的一种优化变体，它通过将所有数据集中在叶子节点，并通过链表连接这些叶子节点，从而显著提升了 范围查询效率 和 磁盘 I/O 性能。

1. 所有数据都存储在叶子节点中

   • 内部节点只包含索引键和子节点指针；

   • 叶子节点存储实际的数据记录或指向数据的指针。

2. 叶子节点之间通过链表连接

   • 支持快速的顺序访问和范围查询。

3. 内部节点不存储数据

   • 提高了每个节点可以容纳的索引数量，减少树的高度。

4. 所有查找最终都会落到叶子节点

   • 确保每次查找路径长度一致，提高性能可预测性。

8. b+ 树的“扇出”是什么意思？扇出数量大有什么好处？

在 B+ 树 中，扇出（Fan-out）指的是一个节点可以拥有的 最大子节点数量，通常由 节点的大小 和 键值（Key）与指针（Pointer）的大小 决定。

B+ 树的扇出越大，性能越好。

9. b+树中的索引信息是不是会有冗余，这个冗余有什么作用

在 B+ 树 中，索引信息确实存在一定程度的 冗余设计，这种冗余是 有意为之 的，并且在数据检索性能和结构平衡方面起到了关键作用。

一、B+ 树中索引冗余的表现形式

1. 父节点中的键值是子节点键值的“复制”

• 内部节点（非叶子节点）中的键值并不存储完整数据，而是作为指引查找路径的索引。

• 这些键值通常出现在子节点中，因此形成了 键值的重复出现。

二、为什么允许索引冗余？它的作用是什么？

虽然 B+ 树看起来有“重复”，但这种冗余具有明确的目的和优势：

1. 提高查询效率

• 索引冗余使得每个内部节点可以快速判断下一步要访问哪个子节点；

• 不需要回溯或深入多个层级来获取完整的索引信息。

2. 减少树的高度

• 冗余索引让每个节点可以容纳更多键值，从而增加扇出；

• 扇出越大，树的高度越低；

• 树高度越低，磁盘 I/O 次数越少，查询更快。

3. 支持高效的范围查询

• 所有数据都在叶子节点，并通过链表连接；

• 索引冗余帮助快速定位起始叶子节点；

• 一旦找到起点，就可以顺序访问后续叶子节点。

4. 简化分裂与合并操作

• 分裂时只需提取中间键值提升到父节点；

• 合并时也能根据冗余索引快速调整父子节点关系；

• 不需要重新计算整个索引结构。

10. b+树中叶子节点之间的链表有什么作用

1. 支持高效的范围查询

• 所有数据都存储在叶子节点中；

• 链表允许从一个叶子节点快速跳转到下一个相邻的叶子节点；

• 实现如 WHERE id BETWEEN 10 AND 50 这类查询时，无需回溯父节点。

2. 提高顺序访问效率

• 数据库经常需要按主键顺序读取大量记录（如分页查询）；

• 链表结构使得全表扫描（Full Scan）更高效；

• 与磁盘 I/O 特性匹配良好（连续读取比随机读取快得多）。

3. 简化索引合并操作

• 多个查询结果可以通过链表快速合并；

• 如执行多个索引条件的联合查询时，可以按链表顺序合并结果集。

4. 便于缓存优化

• 叶子节点链表结构有助于预取（Prefetching）；

• 数据库引擎可以在访问当前叶子节点后，提前加载后续节点内容到缓存中；

• 提高命中率，减少磁盘访问。

11. mysql默认存储引擎使用的b树还是b+树

MySQL 的默认存储引擎是 InnoDB，而 InnoDB 使用的是 B+ 树（B-Plus Tree）作为其索引结构。

12. 创建一个表格，用于记录学生成绩，要求记录姓名，语文，数学，英语，小组，插入30条随机数据，每10人为一个小组，共3个小组，没科成绩最高100分，最低0分。

-- 创建学生成绩表
CREATE TABLE student_scores (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(50) NOT NULL,
    chinese INT CHECK (chinese BETWEEN 0 AND 100),
    math INT CHECK (math BETWEEN 0 AND 100),
    english INT CHECK (english BETWEEN 0 AND 100),
    group_id INT CHECK (group_id BETWEEN 1 AND 3)
);

-- 创建存储过程用于批量插入数据
DELIMITER $$

CREATE PROCEDURE InsertStudentData()
BEGIN
    DECLARE i INT DEFAULT 1;
    DECLARE group_id INT DEFAULT 1;

    WHILE i <= 30 DO
        INSERT INTO student_scores (name, chinese, math, english, group_id)
        VALUES (
            CONCAT('学生', i),
            FLOOR(RAND() * 101),
            FLOOR(RAND() * 101),
            FLOOR(RAND() * 101),
            group_id
        );

        -- 每10条记录切换一个小组
        IF i % 10 = 0 THEN
            SET group_id = group_id + 1;
        END IF;

        SET i = i + 1;
    END WHILE;
END$$

DELIMITER ;

-- 调用存储过程插入数据
CALL InsertStudentData();

13. 按照语文分数进行排名，要求输出排名，分数，姓名，小组名

SELECT 
    @rank := @rank + 1 AS `rank`,
    t.chinese AS score,
    t.name,
    t.group_id AS group_name
FROM 
    (SELECT chinese, name, group_id FROM student_scores ORDER BY chinese DESC) AS t,
    (SELECT @rank := 0) AS r;

14. 计算查询表中的总分，并进行排名，要求输入排名，小组，姓名，总分

SELECT 
    ROW_NUMBER() OVER (ORDER BY (chinese + math + english) DESC) AS `rank`,
    group_id AS group_name,
    name,
    (chinese + math + english) AS total_score
FROM student_scores
ORDER BY total_score DESC;

15. 计算查询各个小组的总分平均分，并对小组进行排名，输出排名及小组的平均分

SELECT 
    ROW_NUMBER() OVER (ORDER BY AVG(chinese + math + english) DESC) AS `rank`,
    group_id,
    ROUND(AVG(chinese + math + english), 2) AS avg_score
FROM student_scores
GROUP BY group_id
ORDER BY avg_score DESC;

16. 查询每个小组中数学最高分的学生姓名和分数

SELECT group_id, name, math
FROM (
    SELECT 
        group_id,
        name,
        math,
        ROW_NUMBER() OVER (PARTITION BY group_id ORDER BY math DESC) AS rn
    FROM student_scores
) AS ranked
WHERE rn = 1;

17. 查询所有总分大于所在小组平均分的学生

SELECT t.name, t.group_id, (t.chinese + t.math + t.english) AS total_score, g.avg_score
FROM student_scores t
JOIN (
    SELECT group_id, AVG(chinese + math + english) AS avg_score
    FROM student_scores
    GROUP BY group_id
) AS g ON t.group_id = g.group_id
WHERE (t.chinese + t.math + t.english) > g.avg_score;

18. 查询每个小组中各科成绩都最高的学生姓名和成绩

SELECT t1.group_id, t1.name, t1.chinese, t1.math, t1.english
FROM student_scores t1
WHERE NOT EXISTS (
    SELECT 1
    FROM student_scores t2
    WHERE t1.group_id = t2.group_id
      AND (t1.chinese < t2.chinese OR t1.math < t2.math OR t1.english < t2.english)
);

19. 按小组对学生进行分组，并计算每个小组中，每科成绩高于 80 分的学生数量

SELECT 
    group_id,
    SUM(CASE WHEN chinese > 80 THEN 1 ELSE 0 END) AS chinese_above_80,
    SUM(CASE WHEN math > 80 THEN 1 ELSE 0 END) AS math_above_80,
    SUM(CASE WHEN english > 80 THEN 1 ELSE 0 END) AS english_above_80
FROM student_scores
GROUP BY group_id
ORDER BY group_id;

20. 查询每个小组中，总分与小组平均分差距最大的学生姓名、总分和差距

SELECT t.group_id, t.name, t.total_score, t.diff_to_avg
FROM (
    SELECT 
        sc.group_id,
        sc.name,
        (sc.chinese + sc.math + sc.english) AS total_score,
        ROUND(
            ABS((sc.chinese + sc.math + sc.english) - g.avg_total), 2
        ) AS diff_to_avg
    FROM student_scores sc
    JOIN (
        SELECT group_id, AVG(chinese + math + english) AS avg_total
        FROM student_scores
        GROUP BY group_id
    ) AS g ON sc.group_id = g.group_id
) AS t
JOIN (
    SELECT group_id, MAX(ABS((chinese + math + english) - avg_total)) AS max_diff
    FROM (
        SELECT 
            sc.group_id,
            (chinese + math + english) AS total_score,
            g.avg_total
        FROM student_scores sc
        JOIN (
            SELECT group_id, AVG(chinese + math + english) AS avg_total
            FROM student_scores
            GROUP BY group_id
        ) AS g ON sc.group_id = g.group_id
    ) AS diffs
    GROUP BY group_id
) AS m
ON t.group_id = m.group_id AND t.diff_to_avg = m.max_diff;