1. 树形结构基础认知树形结构是计算机科学中最基础也最重要的数据结构之一它模拟了自然界中树的形态由节点和边组成。每个节点可以有零个或多个子节点但只有一个父节点根节点除外。这种层次化的组织形式让它在数据存储和检索方面展现出独特优势。在实际开发中树形结构几乎无处不在。从操作系统的文件目录到数据库索引从游戏场景管理到UI组件层级树的身影随处可见。特别是在面试场景中对树的理解深度往往能直接反映一个程序员的基础功底。1.1 为什么需要树形结构相比线性的数组和链表树形结构在以下场景具有明显优势快速查找有序二叉树可以在O(log n)时间内完成查找比线性结构的O(n)快得多动态扩展插入和删除操作不需要移动大量元素只需调整局部指针层次关系天然适合表示具有层级关系的数据如组织架构、文件系统排序效率中序遍历二叉搜索树可以直接得到有序序列提示当面试官问为什么用树不用数组时可以从时间复杂度、内存连续性、扩展成本三个维度对比回答1.2 树的基本术语解析理解树需要掌握这些核心概念根节点(Root)没有父节点的顶层节点叶子节点(Leaf)没有子节点的末端节点度(Degree)节点拥有的子树数量深度(Depth)根节点到该节点的路径长度高度(Height)节点到最远叶子节点的路径长度兄弟节点(Sibling)具有相同父节点的节点以二叉树为例A ← 根节点(深度0) / \ B C ← A的子节点(深度1), B和C互为兄弟节点 / \ \ D E F ← D,E,F为叶子节点(深度2)B节点的度为2有D和E两个子节点这棵树的高度为2从A到D/E/F的最长路径2. 二叉树与二叉搜索树2.1 二叉树基本特性二叉树是每个节点最多有两个子节点的树结构这两个子节点分别称为左子节点和右子节点。二叉树有以下重要特性第i层最多有2^(i-1)个节点深度为k的二叉树最多有2^k - 1个节点叶子节点数 度为2的节点数 1二叉树的遍历方式有三种经典方法# 前序遍历根→左→右 def preorder(root): if root: print(root.val) preorder(root.left) preorder(root.right) # 中序遍历左→根→右 def inorder(root): if root: inorder(root.left) print(root.val) inorder(root.right) # 后序遍历左→右→根 def postorder(root): if root: postorder(root.left) postorder(root.right) print(root.val)2.2 二叉搜索树(BST)实战二叉搜索树是一种特殊的二叉树满足左子树所有节点值 根节点值右子树所有节点值 根节点值左右子树也都是BSTBST的查找操作非常高效public TreeNode searchBST(TreeNode root, int val) { if (root null || root.val val) return root; return val root.val ? searchBST(root.left, val) : searchBST(root.right, val); }BST的插入需要注意保持有序性def insert(root, val): if not root: return TreeNode(val) if val root.val: root.left insert(root.left, val) else: root.right insert(root.right, val) return rootBST的删除操作有三种情况删除叶子节点直接移除删除只有一个子节点的节点用子节点替代删除有两个子节点的节点用右子树的最小值替代常见面试陷阱BST最坏情况下会退化成链表当插入有序序列时查找效率降为O(n)3. 平衡二叉树进阶3.1 AVL树严格平衡的守护者AVL树通过平衡因子左右子树高度差维护平衡要求每个节点的平衡因子绝对值不超过1。当插入或删除破坏平衡时通过四种旋转操作恢复平衡左旋用于右右失衡右旋用于左左失衡左右旋先左旋后右旋用于左右失衡右左旋先右旋后左旋用于右左失衡旋转示例左旋y x / \ / \ x T3 z y / \ --(左旋 y)-- / \ / \ z T2 T1 T2 T3 T4 \ T13.2 红黑树工程实践的王者红黑树通过五个规则保持近似平衡节点是红或黑根节点是黑叶子节点(NIL)是黑红节点的子节点必须是黑从任一节点到叶子节点的路径包含相同数量的黑节点红黑树相比AVL树的优势插入最多需要2次旋转删除最多需要3次旋转适合频繁修改的场景Java中的TreeMap就是红黑树的典型实现// TreeMap核心源码片段 private void fixAfterInsertion(EntryK,V x) { x.color RED; while (x ! null x ! root x.parent.color RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { EntryK,V y rightOf(parentOf(parentOf(x))); if (colorOf(y) RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x parentOf(parentOf(x)); } else { if (x rightOf(parentOf(x))) { x parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { // 对称操作... } } root.color BLACK; }4. B树家族与数据库索引4.1 B树磁盘友好的多路平衡树B树的特点每个节点最多m个子节点m阶B树除根节点外每个节点至少有⌈m/2⌉个子节点所有叶子节点在同一层节点中关键字按升序排列3阶B树示例[10, 20] / | \ [5,8] [15,18] [25,30]B树的插入过程需要特别注意节点分裂从根节点开始找到合适的叶子节点插入后如果节点关键字数超过m-1则分裂中间关键字上升到父节点分裂后的两个节点各自保留一半关键字4.2 B树数据库索引的标准答案B树在B树基础上做了关键改进内部节点只存索引不存数据叶子节点包含全部关键字信息叶子节点通过指针连接形成链表MySQL InnoDB的B树索引结构内部节点(索引) / | \ 叶子节点1 → 叶子节点2 → 叶子节点3 (key指针) (key数据) (key数据)B树相比B树的优势I/O效率更高内部节点不存数据一个页能放更多索引查询更稳定任何查询都要走到叶子节点范围查询更快叶子节点链表支持顺序访问4.3 B*树空间利用率的极致优化B*树在B树基础上非根内部节点增加指向兄弟的指针节点利用率从1/2提升到2/3分裂时优先向兄弟节点转移数据B*树的分裂策略兄弟节点未满时转移部分数据到兄弟节点兄弟节点已满时创建新节点并均分数据相比B树减少了约1/3的分裂操作5. 面试高频问题解析5.1 经典问题与解题思路问题1B树为什么比红黑树更适合数据库索引解题要点磁盘I/O角度B树节点大小通常设计为磁盘页大小(如16KB)高度对比千万级数据B树只需3层红黑树需要24层范围查询B树叶子节点链表支持高效范围扫描问题2MySQL索引什么情况下会失效常见失效场景不符合最左前缀原则如联合索引(a,b,c)但条件只有b1使用函数或运算WHERE YEAR(create_time)2023类型不一致字符串列用数字查询使用OR条件且部分列无索引LIKE以通配符开头LIKE %abc问题3一棵3层B树能存多少数据计算方法假设页大小16KB主键8B指针6B每个索引条目约14B一页可存约1170个根节点1170个索引第二层1170×1170≈137万页叶子层每页假设存100条记录总记录数约137万×1001.37亿5.2 手写算法题准备二叉树层序遍历def levelOrder(root): if not root: return [] queue [root] res [] while queue: level [] for _ in range(len(queue)): node queue.pop(0) level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res验证二叉搜索树public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long min, long max) { if (node null) return true; if (node.val min || node.val max) return false; return validate(node.left, min, node.val) validate(node.right, node.val, max); }红黑树插入实现要点按BST规则插入新节点红色检查父节点颜色如果父节点是黑色直接完成如果父节点是红色检查叔叔节点颜色根据不同情况执行变色和旋转操作在实际工程中理解这些树结构的特性和应用场景远比死记硬背算法实现更重要。建议在准备面试时多思考各种树结构的设计哲学和适用场景这样在面对为什么用这个不用那个之类的问题时才能给出有深度的回答。
树形结构、二叉树与B+树在数据库索引中的应用
1. 树形结构基础认知树形结构是计算机科学中最基础也最重要的数据结构之一它模拟了自然界中树的形态由节点和边组成。每个节点可以有零个或多个子节点但只有一个父节点根节点除外。这种层次化的组织形式让它在数据存储和检索方面展现出独特优势。在实际开发中树形结构几乎无处不在。从操作系统的文件目录到数据库索引从游戏场景管理到UI组件层级树的身影随处可见。特别是在面试场景中对树的理解深度往往能直接反映一个程序员的基础功底。1.1 为什么需要树形结构相比线性的数组和链表树形结构在以下场景具有明显优势快速查找有序二叉树可以在O(log n)时间内完成查找比线性结构的O(n)快得多动态扩展插入和删除操作不需要移动大量元素只需调整局部指针层次关系天然适合表示具有层级关系的数据如组织架构、文件系统排序效率中序遍历二叉搜索树可以直接得到有序序列提示当面试官问为什么用树不用数组时可以从时间复杂度、内存连续性、扩展成本三个维度对比回答1.2 树的基本术语解析理解树需要掌握这些核心概念根节点(Root)没有父节点的顶层节点叶子节点(Leaf)没有子节点的末端节点度(Degree)节点拥有的子树数量深度(Depth)根节点到该节点的路径长度高度(Height)节点到最远叶子节点的路径长度兄弟节点(Sibling)具有相同父节点的节点以二叉树为例A ← 根节点(深度0) / \ B C ← A的子节点(深度1), B和C互为兄弟节点 / \ \ D E F ← D,E,F为叶子节点(深度2)B节点的度为2有D和E两个子节点这棵树的高度为2从A到D/E/F的最长路径2. 二叉树与二叉搜索树2.1 二叉树基本特性二叉树是每个节点最多有两个子节点的树结构这两个子节点分别称为左子节点和右子节点。二叉树有以下重要特性第i层最多有2^(i-1)个节点深度为k的二叉树最多有2^k - 1个节点叶子节点数 度为2的节点数 1二叉树的遍历方式有三种经典方法# 前序遍历根→左→右 def preorder(root): if root: print(root.val) preorder(root.left) preorder(root.right) # 中序遍历左→根→右 def inorder(root): if root: inorder(root.left) print(root.val) inorder(root.right) # 后序遍历左→右→根 def postorder(root): if root: postorder(root.left) postorder(root.right) print(root.val)2.2 二叉搜索树(BST)实战二叉搜索树是一种特殊的二叉树满足左子树所有节点值 根节点值右子树所有节点值 根节点值左右子树也都是BSTBST的查找操作非常高效public TreeNode searchBST(TreeNode root, int val) { if (root null || root.val val) return root; return val root.val ? searchBST(root.left, val) : searchBST(root.right, val); }BST的插入需要注意保持有序性def insert(root, val): if not root: return TreeNode(val) if val root.val: root.left insert(root.left, val) else: root.right insert(root.right, val) return rootBST的删除操作有三种情况删除叶子节点直接移除删除只有一个子节点的节点用子节点替代删除有两个子节点的节点用右子树的最小值替代常见面试陷阱BST最坏情况下会退化成链表当插入有序序列时查找效率降为O(n)3. 平衡二叉树进阶3.1 AVL树严格平衡的守护者AVL树通过平衡因子左右子树高度差维护平衡要求每个节点的平衡因子绝对值不超过1。当插入或删除破坏平衡时通过四种旋转操作恢复平衡左旋用于右右失衡右旋用于左左失衡左右旋先左旋后右旋用于左右失衡右左旋先右旋后左旋用于右左失衡旋转示例左旋y x / \ / \ x T3 z y / \ --(左旋 y)-- / \ / \ z T2 T1 T2 T3 T4 \ T13.2 红黑树工程实践的王者红黑树通过五个规则保持近似平衡节点是红或黑根节点是黑叶子节点(NIL)是黑红节点的子节点必须是黑从任一节点到叶子节点的路径包含相同数量的黑节点红黑树相比AVL树的优势插入最多需要2次旋转删除最多需要3次旋转适合频繁修改的场景Java中的TreeMap就是红黑树的典型实现// TreeMap核心源码片段 private void fixAfterInsertion(EntryK,V x) { x.color RED; while (x ! null x ! root x.parent.color RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { EntryK,V y rightOf(parentOf(parentOf(x))); if (colorOf(y) RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x parentOf(parentOf(x)); } else { if (x rightOf(parentOf(x))) { x parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { // 对称操作... } } root.color BLACK; }4. B树家族与数据库索引4.1 B树磁盘友好的多路平衡树B树的特点每个节点最多m个子节点m阶B树除根节点外每个节点至少有⌈m/2⌉个子节点所有叶子节点在同一层节点中关键字按升序排列3阶B树示例[10, 20] / | \ [5,8] [15,18] [25,30]B树的插入过程需要特别注意节点分裂从根节点开始找到合适的叶子节点插入后如果节点关键字数超过m-1则分裂中间关键字上升到父节点分裂后的两个节点各自保留一半关键字4.2 B树数据库索引的标准答案B树在B树基础上做了关键改进内部节点只存索引不存数据叶子节点包含全部关键字信息叶子节点通过指针连接形成链表MySQL InnoDB的B树索引结构内部节点(索引) / | \ 叶子节点1 → 叶子节点2 → 叶子节点3 (key指针) (key数据) (key数据)B树相比B树的优势I/O效率更高内部节点不存数据一个页能放更多索引查询更稳定任何查询都要走到叶子节点范围查询更快叶子节点链表支持顺序访问4.3 B*树空间利用率的极致优化B*树在B树基础上非根内部节点增加指向兄弟的指针节点利用率从1/2提升到2/3分裂时优先向兄弟节点转移数据B*树的分裂策略兄弟节点未满时转移部分数据到兄弟节点兄弟节点已满时创建新节点并均分数据相比B树减少了约1/3的分裂操作5. 面试高频问题解析5.1 经典问题与解题思路问题1B树为什么比红黑树更适合数据库索引解题要点磁盘I/O角度B树节点大小通常设计为磁盘页大小(如16KB)高度对比千万级数据B树只需3层红黑树需要24层范围查询B树叶子节点链表支持高效范围扫描问题2MySQL索引什么情况下会失效常见失效场景不符合最左前缀原则如联合索引(a,b,c)但条件只有b1使用函数或运算WHERE YEAR(create_time)2023类型不一致字符串列用数字查询使用OR条件且部分列无索引LIKE以通配符开头LIKE %abc问题3一棵3层B树能存多少数据计算方法假设页大小16KB主键8B指针6B每个索引条目约14B一页可存约1170个根节点1170个索引第二层1170×1170≈137万页叶子层每页假设存100条记录总记录数约137万×1001.37亿5.2 手写算法题准备二叉树层序遍历def levelOrder(root): if not root: return [] queue [root] res [] while queue: level [] for _ in range(len(queue)): node queue.pop(0) level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res验证二叉搜索树public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long min, long max) { if (node null) return true; if (node.val min || node.val max) return false; return validate(node.left, min, node.val) validate(node.right, node.val, max); }红黑树插入实现要点按BST规则插入新节点红色检查父节点颜色如果父节点是黑色直接完成如果父节点是红色检查叔叔节点颜色根据不同情况执行变色和旋转操作在实际工程中理解这些树结构的特性和应用场景远比死记硬背算法实现更重要。建议在准备面试时多思考各种树结构的设计哲学和适用场景这样在面对为什么用这个不用那个之类的问题时才能给出有深度的回答。
