JavaGuide（7）
MySQL索引详解
索引
索引是一种用于快速查询和检索数据的数据结构，其本质可以看成是一种排序好的数据结构。
索引的优缺点
优点：
- 使用索引可以大大加快数据的检索速度（大大减少检索的数据量）, 减少 IO 次数，这也是创建索引的最主要的原因。
- 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
缺点：
- 创建索引和维护索引需要耗费许多时间。当对表中的数据进行增删改的时候，如果数据有索引，那么索引也需要动态的修改，会降低 SQL 执行效率。
- 索引需要使用物理文件存储，也会耗费一定空间。
索引底层数据结构选型
Hash 表
哈希表是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。
为何能够通过 key 快速取出 value 呢？ 原因在于 哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到 key 对应的 index，找到了 index 也就找到了对应的 value。
hash = hashfunc(key)
index = hash % array_size
哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
减少 Hash 冲突的发生，一个好的哈希函数应该“均匀地”将数据分布在整个可能的哈希值集合中。
二叉查找树
二叉查找树（Binary Search Tree，简称BST），又称二叉搜索树或二叉排序树，是一种特殊的二叉树数据结构。以下是对二叉查找树的详细介绍：
一、定义与性质
- 定义：
- 二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
- 性质：
- 每个节点最多有两个子节点，分别称为左子节点和右子节点。
- 对于树中的任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值，保证有序性。
- 在标准的二叉查找树中，没有两个节点的值是相同的。
- 左右子树也都是二叉查找树。
二、基本操作
- 查找：
- 从根节点开始，比较当前节点的值与目标值。
- 如果当前节点的值等于目标值，查找成功。
- 如果当前节点的值大于目标值，则在左子树中继续查找。
- 如果当前节点的值小于目标值，则在右子树中继续查找。
- 如果到达了叶子节点还没有找到目标值，则查找失败。
- 插入：
- 从根节点开始，遵循查找的规则，直到找到合适的空位置插入新节点。
- 删除：
- 如果被删除的节点是叶子节点，直接删除。
- 如果被删除的节点只有一个子节点，用其子节点替代它。
- 如果被删除的节点有两个子节点，找到它的中序后继（右子树中的最小节点）或中序前驱（左子树中的最大节点）来替代它，然后删除中序后继或前驱节点。
三、时间复杂度与空间复杂度
- 时间复杂度：
- 在平衡的情况下，对于含有n个节点的二叉查找树，查找、插入和删除操作的时间复杂度均为O(log n)。
- 最坏情况下，即树不平衡的情况下（例如退化成一条链表），这些操作的时间复杂度可能会退化到O(n)。
- 空间复杂度：
- 二叉查找树的空间复杂度是O(n)，因为它需要存储n个节点。
四、应用场景与优势
- 应用场景：
- 二叉查找树在各种算法和程序设计中都有广泛的应用，如数据库索引、编译器符号表等。
- 它也作为其他高级数据结构的基础，如平衡二叉树（AVL树、红黑树）等的实现都离不开对二叉查找树的理解和运用。
- 优势：
- 二叉查找树具有快速的查找、插入和删除操作，特别是在平衡的情况下。
- 它结合了链表的快速插入与删除操作的特点和数组快速查找的优势。
AVL 树
AVL树是一种自平衡的二叉搜索树，由两位前苏联的数学家G.M. Adelson-Velsky和E.M. Landis在1962年提出。以下是对AVL树的详细介绍：
一、定义与性质
- 定义：
- AVL树是一种二叉搜索树，它的每个节点都有一个平衡因子，定义为该节点的左子树的高度减去右子树的高度。
- AVL树的平衡因子的绝对值不超过1，即任意节点的左右子树高度差不超过1。
- AVL树中任意节点的左子树和右子树也都是AVL树。
- 性质：
- 由于AVL树的平衡性，它能够保持树的高度在一个较小的范围内，从而提高了搜索、插入和删除操作的效率。
- 在最坏情况下，AVL树的操作时间复杂度仍然保持在O(log n)级别。
二、基本操作
- 查找：
- AVL树的查找操作与二叉搜索树相同，从根节点开始，根据目标值与当前节点值的比较结果，在左子树或右子树中递归查找。
- 由于AVL树的高度平衡性，查找操作的时间复杂度为O(log n)。
- 插入：
- 插入操作首先按照二叉搜索树的插入规则找到新节点的插入位置。
- 然后，从插入节点开始，自底向上更新节点的平衡因子，并检查是否需要旋转来保持树的平衡。
- 如果需要旋转，根据平衡因子的不同，可能进行左旋转、右旋转、左右双旋转或右左双旋转。
- 插入操作的时间复杂度为O(log n)。
- 删除：
- 删除操作首先按照二叉搜索树的删除规则找到并删除目标节点。
- 然后，从被删除节点的父节点开始，自底向上更新节点的平衡因子，并检查是否需要旋转来保持树的平衡。
- 如果需要旋转，同样根据平衡因子的不同进行相应的旋转操作。
- 删除操作的时间复杂度也为O(log n)。
三、旋转操作
- 左旋转：
- 当某个节点的平衡因子为2，且其左子树的平衡因子为1或0时，进行左旋转。
- 左旋转将当前节点向左旋转，使其右子节点成为新的根节点，原根节点成为新根节点的左子节点，新根节点的左子节点成为原根节点的右子节点。
- 右旋转：
- 当某个节点的平衡因子为-2，且其右子树的平衡因子为-1或0时，进行右旋转。
- 右旋转将当前节点向右旋转，使其左子节点成为新的根节点，原根节点成为新根节点的右子节点，新根节点的右子节点成为原根节点的左子节点。
- 左右双旋转：
- 当某个节点的平衡因子为2，且其左子树的平衡因子为-1时，进行左右双旋转。
- 左右双旋转首先对当前节点的左子节点进行右旋转，然后再对当前节点进行左旋转。
- 右左双旋转：
- 当某个节点的平衡因子为-2，且其右子树的平衡因子为1时，进行右左双旋转。
- 右左双旋转首先对当前节点的右子节点进行左旋转，然后再对当前节点进行右旋转。
四、应用场景与优势
- 应用场景：
- AVL树广泛应用于需要高效搜索、插入和删除操作的场景，如数据库索引、编译器中的符号表、内存管理等。
- 它也常用于实现其他高级数据结构，如平衡二叉树、红黑树等的底层实现。
- 优势：
- AVL树通过旋转操作保持树的平衡性，从而保证了在最坏情况下仍然具有高效的搜索、插入和删除操作。
- 与其他平衡二叉树相比，AVL树的实现相对简单且易于理解。
红黑树
红黑树（Red Black Tree）是一种自平衡的二叉查找树，它在计算机科学领域有广泛的应用。以下是对红黑树的详细介绍：
一、定义与性质
- 定义：
- 红黑树是一种每个节点都带有颜色属性的二叉查找树，颜色或为红色或为黑色。
- 它通过特定的规则和旋转操作来保持树的平衡性。
- 性质：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 所有叶子节点（NIL节点）是黑色。
- 每个红色节点的两个子节点都是黑色（即不能有两个连续的红色节点）。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些性质确保了红黑树的高度大致平衡，从而保证了查找、插入和删除操作的时间复杂度可以稳定地达到O(log n)级别，其中n是树中节点的数量。
二、基本操作
- 查找：
- 红黑树的查找操作与普通的二叉查找树相同。
- 从根节点开始，根据目标值与当前节点值的比较结果，在左子树或右子树中递归查找。
- 插入：
- 插入操作首先按照二叉查找树的插入规则找到新节点的插入位置。
- 然后，将新节点插入到树中，并将其颜色设置为红色。
- 插入后，可能需要通过一系列的旋转和重新着色操作来保持红黑树的性质。
- 删除：
- 删除操作相对复杂，需要找到要删除的节点，并根据节点的颜色和其子节点的情况进行不同的处理。
- 删除后，同样需要通过旋转和重新着色操作来保持红黑树的性质。
三、旋转操作
红黑树的旋转操作包括左旋和右旋，这些操作用于在插入或删除节点后重新平衡树。
- 左旋：
- 左旋操作将某个节点的右子节点上移，使其成为新的父节点，而原父节点则成为新父节点的左子节点。
- 右旋：
- 右旋操作与左旋相反，将某个节点的左子节点上移，使其成为新的父节点，而原父节点则成为新父节点的右子节点。
四、应用场景与优势
- 应用场景：
- 红黑树广泛应用于各种需要高效查找、插入和删除操作的场景。
- 例如，在操作系统中用于进程管理和内存管理，在编译器中用于实现符号表，在数据库系统中用于实现索引等。
- 优势：
- 红黑树通过其平衡性和旋转操作保证了高效的查找、插入和删除操作。
- 与其他平衡二叉树相比，红黑树的实现相对简单且易于理解。
- 红黑树在插入和删除操作时的平衡调整代价较低，因此在实际应用中具有较高的效率。
五、与AVL树的区别
- 平衡性：
- AVL树要求每个节点的左右子树高度差不超过1，而红黑树则通过颜色和特定的规则来保持平衡性。
- AVL树的平衡性更加严格，因此在某些情况下可能导致更多的旋转操作。
- 旋转操作：
- AVL树在插入和删除节点时可能需要进行单旋转或双旋转操作来保持平衡性。
- 红黑树则通过左旋和右旋操作以及重新着色来保持平衡性。
- 应用场景：
- AVL树更适用于需要频繁进行查找操作的场景，因为其平衡性保证了查找效率的稳定。
- 红黑树则更适用于需要频繁进行插入和删除操作的场景，因为其平衡调整代价较低且效率较高。
B树& B+树
B树和B+树是计算机科学中两种重要的自平衡树数据结构，它们广泛应用于数据库、文件系统等领域，以实现高效的存储和检索操作。以下是对B树和B+树的详细介绍：
一、B树
- 定义：
在计算机科学中，B树（B-tree）是一种自平衡的树数据结构，能够保持数据有序。B树是一个一般化的二叉查找树（binary search tree），但不同的是，B树可以拥有多于2个子节点。
-
特性：
- B树的内部（非叶子）节点可以拥有可变数量的子节点，数量范围预先定义好。
- B树为系统大块数据的读写操作做了优化，减少了定位记录时所经历的中间过程，从而加快了存取速度。
- B树这种数据结构可以用来描述外部存储，常被应用在数据库和文件系统的实现上。
-
节点结构：
- 在B树中，每个节点通常包含一定数量的键值，键值的数量被选定在d和2d之间（d为某个正整数）。
- 一个节点的分支（或子节点）的数量会比存储在节点内部键值的数量大1。
-
操作：
- 插入：当数据被插入时，节点的子节点数量会发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。
- 删除：删除操作类似，也需要通过合并或分离节点来维持树的平衡。
二、B+树
- 定义：
B+树（B+ Tree）是一种树数据结构，是B树的一种变形形式，通常用于数据库和操作系统的文件系统中。
-
特性：
- B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
- B+树元素自底向上插入，这与二叉树恰好相反。
- B+树的非叶子节点只存储键值，不存储数据，所有数据都存储在叶子节点上，形成有序链表。
- B+树的所有叶子节点在同一层，因此查询效率相当。
-
节点结构：
- B+树的内部节点只包含键值，用于索引，不存储实际数据。
- 叶子节点包含全部关键字的信息及指向含有这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
-
操作：
- 查找：B+树的查找操作可以从最小关键字起顺序查找，也可以从根节点开始随机查找。在查找时，若非终端节点上的关键值等于给定值，并不终止，而是继续向下直到叶子节点。
- 插入：B+树的插入操作在叶子节点上进行。插入后，如果节点关键字数目超过上限，则节点会分裂成两个节点，并可能影响到父节点。
- 删除：B+树的删除操作也仅在叶子节点进行。删除后，如果节点中关键字的个数少于下限，则可能与兄弟节点合并。
三、B树与B+树的区别
-
结构差异：
- B树的非叶子节点也包含需要查找的有效信息。
- B+树的非叶子节点只包含键值，用于索引，不存储实际数据，所有数据都存储在叶子节点上。
-
应用场景：
- B树更适用于需要频繁在内部节点进行查找和修改操作的场景。
- B+树由于所有数据都存储在叶子节点上，且叶子节点形成有序链表，因此更适用于需要顺序访问和范围查询的场景，如数据库和文件系统的索引。
原文地址：https://blog.csdn.net/y050505/article/details/142977071
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！