面试击穿mysql

Mysql三大范式:

 第一范式（1NF）：

        不符合第一范式的典型情况是在一个字段中存放多种不同类型的详细信息。例如，在商品表中，若将商品名称、价格和类型都存储在同一个字段中，会带来诸多弊端。首先，在进行查询操作时，由于数据混杂在一起，要提取特定信息会变得十分困难。其次，进行数据修改也会非常复杂，容易出错且难以保证数据的一致性。第一范式要求将这些不同类型的数据进行拆分，提取出来后放在不同的字段中，确保每个字段都是不可分割的原子数据项，以便于数据的管理和操作。

 第二范式（2NF）：

      在满足第一范式的基础上，第二范式要求数据库表中的每一个非主属性都完全依赖于主键。当第一范式中存放的商品数据有很多重复时，我们可以给每一列字段添加一个合适的主键来区分这些重复的商品。例如，如果商品表中有商品编号、商品名称、价格、类型等字段，商品编号可以作为主键，确保商品名称、价格和类型等非主属性完全依赖于商品编号这个主键。这样可以避免数据的冗余和不一致性，提高数据的完整性和准确性。

 第三范式（3NF）：

        在满足第二范式的基础上，以商品表为例，将商品的类型等重复数据可以提取出来，生成另一个专门的商品类型表。这个新表可以设置一个主键，比如类型编号，然后在商品表中使用这个类型编号来代替商品表中的商品类型字段。这样可以进一步减少数据冗余，提高数据的一致性和可维护性。

 反范式设计：

         反范式设计是一种违反第三范式的设计方式，它将商品中常用的属性放在商品表中，以牺牲一定的内存空间来换取查询速度，减少连接表查询的开销。在某些特定场景下，这种设计是有意义的。比如，当对商品表的查询操作非常频繁，而连接其他表进行查询会导致性能严重下降时，可以考虑将一些经常一起查询的属性进行反范式设计，存储在商品表中。然而，需要注意的是，反范式设计会增加数据冗余，可能会带来数据一致性的问题。因此，在进行反范式设计时，需要谨慎考虑，并采取适当的措施来确保数据的一致性，比如定期进行数据清理和同步等操作。

二 Mysql的执行原理

   连接器： 身份认证和权限相关(登录 MySQL 的时候)。
• 查询缓存： 执行查询语句的时候，会先查询缓存（MySQL 8.0 版本后移除，因为这个功能不太实用）。
• 分析器： 没有命中缓存的话，SQL 语句就会经过分析器，分析器说白了就是要先看你的 SQL 语句要干嘛，再检查你的 SQL 语句语法是否正确。
• 优化器： 按照 MySQL 认为最优的方案去执行。
• 执行器： 执行语句，然后从存储引擎返回数据。 执行语句之前会先判断是否有权限，如果没有权限的话，就会报错。
• 插件式存储引擎：主要负责数据的存储和读取，采用的是插件式架构，支持 InnoDB、MyISAM、Memory 等多种存储引擎。

算法

1. 顺序查找法

   • 基本概念

     • 顺序查找是一种简单的查找算法。它从数据结构的一端开始，逐个检查元素，直到找到目标元素或者遍历完整个数据结构为止。

     • 例如，在一个数组[3, 7, 1, 9, 4]中查找元素9，就从第一个元素3开始，依次比较每个元素，直到找到9。

   • 时间复杂度

     • 在最坏的情况下，需要遍历整个数据结构。如果数据结构中有 n 个元素，时间复杂度为。例如，要查找的元素在数组的最后一个位置或者不存在于数组中时，就需要比较 n 次。

   • 适用场景

     • 适用于数据量较小或者数据结构没有排序的情况。比如，一个无序的联系人列表，当需要查找某个联系人时，顺序查找是一种简单直接的方法。

2. 二分查找法

   • 基本概念

     • 二分查找要求数据结构是有序的。它每次比较中间元素与目标元素的大小。如果中间元素等于目标元素，则查找成功；如果中间元素大于目标元素，则在左半部分继续查找；如果中间元素小于目标元素，则在右半部分继续查找。

     • 例如，在有序数组[1, 3, 5, 7, 9]中查找5，首先比较中间元素5（中间位置是(0 + 4)/2 = 2），就直接找到了。如果要查找4，比较中间元素5后，发现4 < 5，就在左半部分[1, 3]继续查找。

   • 时间复杂度

     • 每次查找都能将搜索区间缩小一半。对于包含 n 个元素的有序数组，时间复杂度为。这比顺序查找在效率上有很大的提升，尤其是当 n 较大时。

   • 适用场景

     • 适用于数据量较大且数据已经排序的情况，如字典中的单词查找（假设字典内容是按照字母顺序排序的）。

3. Hash 算法

   • 基本概念

     • Hash 算法是一种将任意长度的数据映射为固定长度的哈希值（也称为散列值）的算法。这个哈希值可以作为数据的索引，用于快速存储和检索数据。

     • 例如，一个简单的哈希函数可以是将字符串中每个字符的 ASCII 码相加，然后对一个固定的数取模。假设哈希表大小为 10，对于字符串 “abc”，其 ASCII 码之和为97 + 98+ 99 = 294，294 mod 10 = 4，那么这个字符串就可以存储在哈希表的索引为 4 的位置。

   • 冲突解决

     • 由于不同的数据可能会产生相同的哈希值，这就是哈希冲突。常见的解决方法有开放定址法（如线性探测、二次探测）和链地址法。在链地址法中，当发生冲突时，将具有相同哈希值的数据以链表的形式存储在同一个哈希桶中。

   • 应用场景

     • 在数据库索引、密码存储（存储密码的哈希值而不是密码本身）等领域广泛应用。比如，在数据库中通过哈希算法为用户 ID 生成索引，能够快速定位用户记录。

4. 树

   • 基本概念

     • 树是一种非线性的数据结构，它由节点（Node）和边（Edge）组成。有一个根节点（Root），其余节点可以分为多个子树。树中的节点可以有零个或多个子节点。

     • 例如，一个公司的组织结构可以用树来表示，公司的 CEO 是根节点，各个部门经理是子节点，部门员工是更下一层的子节点。

   • 术语

     • 节点的度（Degree）是指节点拥有的子节点的数量。树的度是树中节点的最大度数。叶子节点（Leaf Node）是度为 0 的节点，即没有子节点的节点。

   • 遍历方式

     • 主要有前序遍历（根节点 - 左子树 - 右子树）、中序遍历（左子树 - 根节点 - 右子树）和后序遍历（左子树 - 右子树 - 根节点）。这些遍历方式在处理树结构的数据时非常重要，比如在解析表达式树等场景。

5. 二叉树

   • 基本概念

     • 二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。

     • 例如，二叉树可以用来表示算术表达式，其中运算符为非叶子节点，操作数为叶子节点。如表达式3 + 4 * 2可以构建成一个二叉树，根节点是+，左子节点是3，右子节点是*（*的左子节点是4，右子节点是2）。

   • 性质

     • 对于一棵完全二叉树（除了最后一层外，每层节点数都达到最大值，最后一层的节点都靠左排列），如果节点数为 n，其深度为。

   • 二叉树的遍历

     • 前序遍历：先访问根节点，再访问左子树，最后访问右子树。中序遍历：先访问左子树，再访问根节点，最后访问右子树。后序遍历：先访问左子树，再访问右子树，最后访问根节点。层次遍历：按照从上到下、从左到右的顺序访问节点。

6. 多叉树

   • 基本概念

     • 多叉树是每个节点可以有多于两个子节点的树。它比二叉树更具一般性。

     • 例如，文件系统的目录结构可以用多叉树来表示，一个目录可以包含多个子目录和文件，这里的目录和文件就相当于树中的节点。

   • 应用场景

     • 在存储层次结构数据，如操作系统中的文件目录结构、XML/HTML 文档的结构解析等场景中有广泛应用。

7. 平衡树

   • 基本概念

     • 平衡树是一种二叉树，它的左右子树的高度差被限制在一定范围内，以保证树的高度不会过高。这样可以保证查找、插入和删除等操作的时间复杂度在最坏情况下仍然能保持在对数级别。

     • 例如，AVL 树是一种平衡树，它的左右子树高度差的绝对值不超过 1。当插入或删除一个节点时，AVL 树会通过旋转操作（左旋和右旋）来调整树的结构，使其保持平衡。

   • 优势

     • 相比于普通二叉树，平衡树在最坏情况下也能提供高效的操作性能。例如，在频繁插入和删除元素的情况下，如果是普通二叉树可能会退化成链表，时间复杂度变为，而平衡树可以保持的时间复杂度。

8. 红黑树

   • 基本概念

     • 红黑树是一种自平衡二叉查找树。它的每个节点都有一个颜色属性（红色或黑色），并且满足以下性质：根节点是黑色；每个叶子节点（NIL 节点）是黑色；如果一个节点是红色的，则它的子节点必须是黑色；从一个节点到其后代叶子节点的所有简单路径上，黑色节点的数量相同。

     • 例如，在 Linux 内核的进程调度等场景中使用红黑树来管理进程优先级队列，以保证高效的插入和删除操作。

   • 操作复杂度

     • 红黑树的插入、删除和查找操作的时间复杂度都是。它通过一系列的变色和旋转操作来保持树的平衡。

   • 与其他平衡树的比较

     • 红黑树不像 AVL 树那样严格要求左右子树的高度差，在插入和删除操作后调整平衡的操作相对简单，性能损耗相对较小，因此在很多实际场景中被广泛应用。

9. B 树

   • 基本概念

     • B 树是一种平衡的多叉树，主要用于磁盘等外存储设备的数据组织。它的每个节点可以有多个子节点和多个关键字。一个节点中的关键字用于划分其子树的范围。

     • 例如，一个 B 树的节点可以存储多个索引值，这些索引值将数据划分为不同的区间，每个区间对应一个子树。

   • 特点

     • B 树的阶数（m）表示一个节点最多可以拥有的子节点数。在 B 树中，所有叶子节点都在同一层，这保证了树的平衡。B 树的查找、插入和删除操作的时间复杂度与树的高度有关，通常为，其中 n 是数据的个数。

   • 应用场景

     • 广泛应用于数据库索引系统，因为它能够减少磁盘 I/O 操作，提高数据存储和检索的效率。

10. B + 树

• 基本概念

  • B + 树是 B 树的一种变体。在 B + 树中，所有的数据都存储在叶子节点中，非叶子节点只存储索引信息。叶子节点之间通过指针相连，形成一个有序链表。

  • 例如，在数据库索引中，B + 树的非叶子节点就像是一本书的目录，只包含关键字和指向子树（下一级目录或具体内容页）的指针，而实际的数据都在叶子节点（具体内容页）中。

• 优势

  • B + 树更适合范围查询。因为叶子节点形成了有序链表，在进行范围查询时，可以通过遍历链表高效地获取范围内的数据。在数据库系统中，对于按照某个范围查询数据（如查询年龄在 20 - 30 岁之间的用户），B + 树的效率很高。