MySQL笔记1

数据结构

b+树

什么是b+树？

B+树是一种常用的数据结构，用于在计算机科学中实现关联数组（例如数据库索引）和排序。它是一种树数据结构，由一个根节点、内部节点和叶节点组成，通常被用于实现关系数据库管理系统中的索引结构。

以下是B+树的主要特点：

1. 平衡性：B+树是一种自平衡树，确保在插入或删除节点时树保持平衡。这使得在大型数据集中的查询操作具有较稳定的性能。
2. 有序性：B+树中的所有叶节点形成一个有序链表，可以按顺序遍历整个数据集。这在范围查询和排序操作中非常有用。
3. 多路搜索：B+树是一种多路搜索树，每个节点可以包含多个子节点。这意味着在查询时可以更快地定位到所需的数据，而不需要遍历整个树。
4. 叶节点存储数据：与其他树结构不同，B+树的关键字只存在于叶节点中，而内部节点只包含关键字的副本以及指向子节点的指针。这样做可以节省内存空间，并提高查询性能。
5. 高扇出性：B+树的节点通常有较高的扇出（即每个节点包含的子节点数量），这有助于减少树的高度，从而提高查询效率。

由于上述特性，B+树在数据库系统中广泛应用于索引结构的实现，以支持高效的数据检索和管理。

B+树和b树有啥区别？

B树（B-tree）和B+树（B+ tree）是两种相似但有着一些关键区别的树数据结构，它们都被广泛应用于数据库索引和文件系统中。以下是它们之间的主要区别：

1. 叶节点存储方式：
   • B树：在B树中，每个节点不仅存储索引键，还存储对应的数据。这意味着在B树中，叶节点不仅包含索引信息，还包含实际的数据。
   • B+树：与B树不同，B+树的叶节点仅存储索引键，而实际的数据则存储在叶节点的外部。这意味着B+树的叶节点只用于索引，而不存储实际数据，这样可以提高范围查询和顺序遍历的效率。
2. 内部节点结构：
   • B树：在B树中，内部节点和叶节点的结构相似，都包含键和指向子节点的指针。
   • B+树：B+树的内部节点仅包含键和指向子节点的指针，而不存储数据。所有的数据都存储在叶节点中。
3. 范围查询和顺序遍历效率：
   • B树：由于B树的叶节点存储了实际数据，因此在范围查询和顺序遍历时，需要遍历整个B树的叶节点以获取所有数据，性能可能较低。
   • B+树：B+树的所有叶节点形成一个有序链表，因此在范围查询和顺序遍历时非常高效，只需遍历叶节点链表即可。
4. 数据插入和删除的影响：
   • B树：由于B树的叶节点存储实际数据，因此在插入和删除数据时可能需要进行数据的移动和重新平衡，涉及的操作较多。
   • B+树：B+树的叶节点仅存储索引键，因此在插入和删除数据时只需调整索引部分，不涉及实际数据的移动，因此通常比B树更高效。

总的来说，B+树相对于B树来说在范围查询、顺序遍历和插入删除等方面具有更好的性能和效率，因此在大多数数据库系统中，B+树更常被用作索引结构的实现。

查找插入以及空间复杂度是什么？

B+树的查找、插入和删除操作的时间复杂度均为 O(log n)，其中 n 是树中节点的数量。空间复杂度取决于B+树的高度和节点的大小，通常情况下为 O(n)。