MySQL算法篇（一）

Hash算法，也称为哈希算法或散列算法，是一种将任意长度的输入（如文本、图片等）通过某种规则转换成固定长度的输出的算法。这个输出通常被称为哈希值、哈希码或哈希摘要。以下是一些关于哈希算法的关键点：

• 不可逆性：理论上，从哈希值不能逆向推导出原始输入数据。
  
• 确定性：对于同一个输入，无论何时何地使用雷同的哈希算法，都会得到雷同的哈希值。
  
• 快速计算：哈希算法通常设计得非常高效，可以快速计算出哈希值。
  
• 抗辩说性：不同的输入应该产生不同的哈希值，即哈希辩说的概率极低。
  
• 雪崩效应：即使是微小的输入变化，也会导致哈希值的明显不同。
  
• 应用广泛：哈希算法在数据存储、暗码学、网络安全、数据完整性验证等范畴有广泛应用。
  

常见的哈希算法包括：

• MD5（Message-Digest Algorithm 5）：一种广泛使用的哈希算法，产生128位的哈希值。但由于已知的安全性题目，MD5已不再推荐用于安全敏感的应用。
  
• SHA（Secure Hash Algorithm）：一系列哈希函数，包括SHA-1、SHA-2（如SHA-256、SHA-512）和SHA-3。SHA-1已不再被认为是安全的，而SHA-2和SHA-3被广泛认为是安全的。
  
• CRC（Cyclic Redundancy Check）：一种用于检测数据传输错误的哈希算法。
  
• bcrypt：一种专为暗码存储设计的哈希算法，它通过使用盐（salt）和多次迭代来增长计算复杂度，从而提高安全性。
  
• Argon2：一种暗码哈希算法，被认为是更安全的替代bcrypt的选择，赢得了暗码哈希竞赛。
  
• BLAKE2：一种快速、安全的哈希算法，设计用于替代旧的BLAKE算法。
  

哈希算法的选择取决于具体的应用场景和安全需求。在安全敏感的应用中，推荐使用那些被认为抗碰撞性更强、更难以被破解的哈希算法。

二叉查找树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有以下特性：

• 有序性：对于树中的任意节点，其左子树上所有节点的值都小于该节点的值，其右子树上所有节点的值都大于该节点的值。
  
• 唯一性：树中的每个节点都有一个唯一的值。
  
• 二叉树结构：每个节点最多有两个子节点，即左子节点和右子节点。
  
• 平衡性：理想情况下，二叉查找树应该是平衡的，即任意两个叶子节点的深度差不凌驾1。但在最坏情况下，如果插入的元素是有序的，那么树将退化成链表，导致性能降落。
  

二叉查找树的根本操纵包括：

• 查找（Search）：在树中查找一个特定的值。由于树的有序性，查找的时间复杂度可以低至O(log n)，最坏情况下为O(n)。
  
• 插入（Insert）：向树中插入一个新的值。插入操纵需要保持树的有序性，时间复杂度平均为O(log n)，最坏情况下为O(n)。
  
• 删除（Delete）：从树中删除一个节点。删除操纵相对复杂，需要思量三种情况：被删除节点没有子节点、有一个子节点、有两个子节点。时间复杂度平均为O(log n)，最坏情况下为O(n)。
  
• 遍历（Traversal）：遍历二叉查找树可以按照不同的次序访问所有节点，常见的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历。中序遍历二叉查找树可以得到一个有序的节点值序列。
  

二叉查找树的变种包括：

• 平衡二叉查找树（Balanced Binary Search Tree）：如AVL树和红黑树，它们通过特定的旋转操纵保持树的平衡，从而保证操纵的时间复杂度始终为O(log n)。
  
• B树和B+树：用于数据库和文件系统的多路查找树，可以有多个子节点。
  
• 区间查找树（Interval Tree）：用于存储区间信息，并快速查询给定区间内的所有点。
  

二叉查找树是一种非常基础且重要的数据结构，广泛应用于算法和计算机科学范畴。

 总结
         在数据库中，数据的自增是一个很常见的形式，好比一个表的主键是 id，而主键一般默认都是自增的，如果采取二叉树这种数据结构作为索引，那上面介绍到的不平衡状态导致的线性查找的题目必然出现。因此，简单的二叉查找树存在不平衡导致的检索性能降低的题目，是不能直接用于实现 Mysql 底层索引的。



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。