mysql学习小记

索引

索引是帮助mysql高效率获取数据的排好序的数据结构

索引的数据结构:

二叉树:

二叉树(Binary Tree)是一种树状数据结构,它由n(n >= 0)个节点组成,每个节点最多有两个子节点,这两个子节点分别被称为左子节点和右子节点。二叉树的节点通常包含一个存储数据的值和两个指向左右子树的指针。
二叉树可以为空树,此时它不包含任何节点。如果二叉树不为空,那么它的根节点就是最顶层的节点,所有其他节点都是从根节点开始不断向下延伸得到的。由于每个节点最多有两个子节点,因此二叉树的每一层最多只有两个节点,所以它是一种非常简单、直观的数据结构。
二叉树有多种不同的形态,包括满二叉树、完全二叉树、平衡二叉树等等。在实际应用中,二叉树常常被用来存储有序数据,例如搜索树、堆等等。二叉树还可以用来实现算法中的许多基本数据结构,例如栈、队列等等。
二叉树的遵循左小右大的原则
下面是一个简单的二叉树示意图:

红黑树:

红黑树是一种自平衡的二叉查找树,它的每个节点上都有一个额外的颜色标识,可以是红色或黑色。红黑树具有以下几个特点:
1.根节点是黑色的;
2.每个叶子节点都是黑色的空节点(NIL节点);
3.如果一个节点是红色的,则它的子节点必须是黑色的;
4.从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点(即具有相同的“黑高度”);
5.新插入的节点为红色节点,并保持红黑树的平衡性质。
这些特点保证了红黑树始终是一棵近似平衡的二叉查找树,可以在 O(log n) 的时间内完成查找、插入、删除等操作。由于其高效、简单、易实现的特点,红黑树被广泛应用于计算机科学的各个领域,例如操作系统、编译器、数据库等。

hash表:
B-Tree:

补充

平衡二叉树:

平衡二叉树是一种二叉树,它满足以下性质:对于任意一个节点,它的左右子树的高度差不超过1。
由于平衡二叉树的高度相对较小,所以在插入、查找、删除等操作的时间复杂度上具有更好的性能表现。常见的平衡二叉树有AVL树、红黑树、Treap等。
平衡二叉树只是一种定义,任意一种满足左右子树的高度差不超过1的二叉树,都成为平衡二叉树
下面是一个简单的平衡二叉树示意图

AVL树:

AVL树是一种自平衡的二叉搜索树。它的特点是每个节点的左子树和右子树的高度差不超过1,因此它也被称为高度平衡树。AVL树是由两位苏联计算机科学家Georgy Adelson-Velsky和Evgenii Landis于1962年发明的,是最早被提出的自平衡树之一。
AVL树和其他自平衡树(例如红黑树)类似,都是为了解决在二叉搜索树中可能出现的不平衡问题,使得树的查找、插入、删除等操作的时间复杂度能够稳定在O(log n)级别。AVL树是通过旋转操作来实现平衡的,具体来说,当树的某个节点的左子树和右子树高度差超过1时,就需要对该节点进行旋转操作来调整树的结构,使其重新达到平衡。
虽然AVL树的平衡性比较好,但是在频繁的插入和删除操作时,需要进行较多的旋转操作,导致性能相对较低。因此在实际应用中,常常采用红黑树等其他自平衡树来代替AVL树。
下面是两种情况的旋转实例

二叉搜索树:

二叉搜索树是一种常用的数据结构,它是一棵二叉树,其中每个节点都包含一个可比较的键值,且满足以下性质:

  1. 每个节点都包含一个可比较的键值;
  2. 左子树中所有节点的键值小于根节点的键值;
  3. 右子树中所有节点的键值大于根节点的键值;
  4. 左右子树都是二叉搜索树;
    由于满足上述性质,二叉搜索树具有较快的查找、插入、删除操作的时间复杂度,其时间复杂度与树的高度相关,理想情况下,插入、删除、查找的时间复杂度均为 O(log n)。
    需要注意的是,二叉搜索树的性质在极端情况下可能会退化,例如,如果插入的键值顺序是递增或递减的,则二叉搜索树将退化成一条链,此时操作的时间复杂度将退化为O(n)。为了避免这种情况的发生,通常需要在插入时采用一些方法(如随机化插入、平衡二叉树等)来保证二叉搜索树的平衡性。

存储引擎

MyISAM

存储引擎为MyISAM的数据表在磁盘中会有三个文件
1.frm 用来存储数据表的表结构信息
2.MYD 用来存储数据表的数据
3.MYI 用来存储数据表的索引

本作品采用《CC 协议》,转载必须注明作者和本文链接
huliuwa
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!