樹

• Binary Search Tree (BST)
  A BST is a tree where each node’s left child has a key value less than the node’s key, and the right child’s key value is greater. 二叉查找树中，每个节点的左子节点的键值小于当前节点，右子节点的键值大于当前节点。

  The top node is called the root, and nodes without children are called leaves. 顶端的节点称为根节点，没有子节点的节点称为叶节点。

• Balanced Binary Tree (AVL Tree)
  An AVL Tree is a BST where the height difference between the left and right subtrees of any node does not exceed one. Searching for nodes has a time complexity of O(log n).
  平衡二叉树（AVL树）是一种满足二叉查找树特性且任意节点的左右子树高度差不超过1的树，其查找节点的时间复杂度为O(log n)。

• Red-Black Tree
  A Red-Black Tree is a self-balancing BST often used in associative arrays. It maintains balance with specific operations on insertion and deletion to optimize search performance, achieving O(log n) for search, insertion, and deletion.
  红黑树是一种自平衡的二叉查找树，常用于实现关联数组，通过插入和删除操作保持平衡，从而优化查找性能，查找、插入和删除操作的时间复杂度为O(log n)。

  • Properties of Red-Black Trees:

    • Nodes are either red or black.
      结点是红色或黑色。
    • The root node is black.
      根结点是黑色。
    • All leaves are black (NIL nodes).
      所有叶子结点是黑色的（NIL结点）。
    • Every red node’s children are black (no two consecutive red nodes on a path).
      每个红色结点的两个子结点都是黑色的（从每个叶子到根的路径中不能有两个连续的红色结点）。
    • All paths from a node to its leaves contain the same number of black nodes.
      从任一结点到每个叶子的所有路径包含相同数量的黑色结点。
    • 新插入的節點一律都為紅色

    

• B Tree (Balanced Tree) In a B Tree, each node (called a page in MySQL) can store multiple keys. It’s designed to minimize disk reads, which makes it more efficient for data retrieval than balanced binary trees. B树中每个节点称为页，每个节点可以存储多个键，减少磁盘读取次数，比平衡二叉树的数据查找效率高。

• B+ Tree (Differences from B Tree) A B+ Tree optimizes the B Tree by storing only indexes in internal nodes, with data only in the leaf nodes. Leaf nodes are connected via linked lists, facilitating range queries. B+树对B树进一步优化，内部节点只存储索引，数据仅存储在叶子节点，叶子节点通过链表连接，便于区间查询。

• Characteristics of B+ Tree

  1. Each node has a maximum of m children and at least m/2 children, except the root node. 每个节点的子节点数量不能超过m，且不少于m/2，根节点例外。
  2. Non-leaf nodes store only keys, while leaf nodes store actual data in a sorted order. 非叶子节点只存储键值，叶子节点存储实际数据，数据按顺序排列。
  3. B+ Trees allow efficient range, ordered, grouped, and deduplicated searches. B+树便于范围查找、排序查找、分组查找和去重查找。