怎么在DW网站站点下建立两张网页服务app开发的公司

怎么在DW网站站点下建立两张网页,服务app开发的公司,聊城做网站的公司流程,内乡微网站建设一、B 树基础概念#xff08;铺垫层#xff09; 知识点梳理 名称定义#xff1a;B 树#xff08;B-tree#xff09;是多叉平衡查找树#xff0c;正确名称为 “B 树”#xff0c;非 “B 阶树”#xff08;“阶” 是 B 树的属性#xff0c;如 m 阶 B 树#xff09;。…一、B 树基础概念铺垫层知识点梳理名称定义B 树B-tree是多叉平衡查找树正确名称为 “B 树”非 “B 阶树”“阶” 是 B 树的属性如 m 阶 B 树。树型对比二叉树体系二叉搜索树BST、AVL 树绝对平衡二叉树、红黑树相对平衡二叉树均为二叉结构。B 树多叉结构平衡特性体现在 “所有叶子节点在同一层”。适用场景哈希、二叉树等结构仅适用于内存数据处理当数据量过大超出内存容量需存储在磁盘外存时B 树为核心解决方案。重点标注【重点】B 树的核心定位多叉 平衡 查找兼具有序性和外存适配性。二叉树与 B 树的本质区别子节点数量二叉 vs 多叉、应用场景内存 vs 外存。难点解析【难点】为何二叉树不适合外存数据处理二叉树的树高随数据量增长呈O(log₂n)趋势如 100 万条数据树高约 20而外存操作的核心成本是磁盘 IO每次 IO 仅能读取一个节点二叉树的高树高会导致大量 IO 次数性能急剧下降。内容扩张补充对比与原理内存 vs 外存性能差异内存访问速度纳秒级10⁻⁹s磁盘 IO 访问速度毫秒级10⁻³s相差约 100 万倍。因此外存操作的核心目标是减少 IO 次数而非单纯减少计算次数。常见树结构适用场景对比表树结构核心特性适用场景二叉搜索树有序无平衡保证少量内存数据、单次查询AVL 树绝对平衡旋转次数多少量内存数据、频繁查询红黑树相对平衡旋转次数少大量内存数据如 Java TreeMapB 树多叉平衡树高低外存数据处理如数据库索引二、磁盘 IO 与 B 树的优势核心价值层知识点梳理磁盘 IO 慢的物理原因磁盘是机械结构由盘片、磁头、扇区组成读取数据时需经历磁头寻道找扇区→盘片旋转定位数据这两个步骤耗时占比超 99%。B 树的优势原理B 树为 “矮胖” 结构多叉导致树高极低可大幅减少磁盘 IO 次数每次 IO 读取一个 B 树节点节点可存储多个关键字。重点标注【重点】磁盘 IO 的性能瓶颈磁头寻道 盘片旋转而非数据传输。B 树 “矮胖” 结构的核心意义降低树高 减少 IO 次数。难点解析【难点】如何量化 B 树的 IO 次数优势以m 阶 B 树和二叉搜索树为例假设存储 n100 万条数据二叉搜索树平衡时树高 hlog₂10⁶≈20 → IO 次数≈20 次m100 阶 B 树根据 B 树树高公式见下文树高 h≈3 → IO 次数≈3 次。结论B 树的 IO 次数呈数量级下降。内容扩张公式与计算m 阶 B 树的树高公式推导基于 B 树性质的最小节点数设 m 阶 B 树的树高为 h根节点为第 1 层则最小总关键字数为Nmin​12×(⌈m/2⌉)h−2×(⌈m/2⌉−1)简化取⌈m/2⌉kn≥12(k−1)(kh−2) → 树高h≤logk​(2(k−1)n−1​)2。实例计算m100k50n10⁶h≤log50​(2×49106−1​)2≈log50​(10204)2≈3验证上述结论。三、B 树的核心性质规则核心层知识点梳理m 阶 B 树m 为树的阶数每个节点最多有 m 个子节点根节点规则关键字数量最少 1 个最多 m-1 个子节点数量最少 2 个最多 m 个。非根节点规则关键字数量最少⌈m/2⌉−1个最多 m-1 个子节点数量最少⌈m/2⌉个最多 m 个子节点数 关键字数 1。关键字关系节点内关键字按升序排列且第 i 个关键字的左子树所有关键字 该关键字右子树所有关键字 该关键字与二叉搜索树一致。叶子节点规则所有叶子节点在同一层平衡的核心体现且叶子节点无子女或视为空节点。重点标注【重点】子节点数与关键字数的关系子节点数 关键字数 1B 树的核心关联规则。关键字的有序性和叶子节点的同层性B 树平衡的两大保证。各节点的关键字 / 子节点数范围需熟记为插入分裂打基础。难点解析【难点】为何非根节点的关键字数下限是⌈m/2⌉−1该下限是为了保证 B 树的平衡特性和最坏情况下的查找效率若下限过低如 1 个可能导致节点分布不均部分节点关键字多部分极少破坏 “矮胖” 结构⌈m/2⌉−1是 “最小平衡阈值”确保节点分裂 / 合并后仍能维持平衡且树高始终保持 O (log_m n) 级别。内容扩张实例验证以 **m3 阶 B 树2-3 树和m4 阶 B 树2-3-4 树** 为例直观理解性质m3k2⌈3/2⌉2非根节点关键字数1~2 个⌈3/2⌉−11m-12子节点数2~3 个实例插入 1,2,3 → 根节点关键字满2 个插入 4 触发分裂中间元素 2 上移为新根1 和 3/4 为子节点叶子节点同层。m4k2⌈4/2⌉2非根节点关键字数1~3 个子节点数2~4 个平衡特性无论插入多少数据叶子节点始终在同一层。四、B 树的插入与分裂机制操作核心层知识点梳理插入前置步骤查找元素是否存在存在则不插入去重若不存在定位到叶子节点插入只能在叶子节点核心规则。插入过程在叶子节点中对关键字进行插入排序保持有序性。分裂触发条件节点关键字数达到 m-1满再插入一个关键字时触发分裂。分裂步骤取节点的中间关键字位置⌊m/2⌋或⌈m/2⌉中间关键字上移到父节点原节点拆分为左、右两个新节点中间关键字左侧为左节点右侧为右节点。树高变化仅当根节点分裂时树高 1普通节点分裂为横向扩展树高不变。重点标注【重点】插入的核心规则只能插在叶子节点区别于二叉树的插入位置。分裂的触发条件关键字数 m原节点满 m-1插入后为 m。分裂的核心步骤中间关键字上移 原节点拆分。难点解析【难点】分裂的递归处理若中间关键字上移后父节点也满了关键字数 m-1则父节点需继续分裂直到根节点根节点分裂后树高 1。中间关键字的选择m 为奇数时中间关键字唯一m 为偶数时通常取⌈m/2⌉位置的关键字如 m4取第 2 个关键字。内容扩张实例演示以m3 阶 B 树为例演示插入序列1,3,5,7,9的完整过程插入 1根节点为 [1]关键字数 1符合规则。插入 3根节点为 [1,3]关键字数 2达到 m-12未分裂。插入 5根节点关键字数 3超出 m-12触发分裂中间关键字 3 上移为新根原节点拆分为 [1]左、[5]右树结构根 [3]子节点 [1]、[5]叶子节点同层。插入 7定位到叶子节点 [5]插入后为 [5,7]关键字数 2未分裂。插入 9定位到叶子节点 [5,7]插入后为 [5,7,9]触发分裂中间关键字 7 上移到父节点 [3]父节点变为 [3,7]原节点拆分为 [5]左、[9]右最终树结构根 [3,7]子节点 [1]、[5]、[9]叶子节点仍在同一层。若继续插入 11定位到 [9]插入后为 [9,11]无分裂插入 13[9,11,13] 触发分裂中间关键字 11 上移到父节点 [3,7]父节点变为 [3,7,11]触发根节点分裂中间关键字 7 上移为新根树高 1。五、B 树的代码实现工程落地层知识点梳理会议提及思路节点定义包含关键字数组、孩子节点数组、父节点引用、记录关键字数量的usedSize。查找方法返回自定义结果类包含节点和下标找到则返回节点和关键字下标未找到则返回父节点和 - 1。插入方法树为空创建根节点插入元素树非空调用查找方法判断元素是否存在不存在则在叶子节点插入插入后检查是否需要分裂。分裂方法处理节点拆分、中间关键字上移、父节点更新。重点标注【重点】节点数据结构设计需同时存储关键字和子节点多叉树的核心且数组大小为 m关键字数组大小 m-1子节点数组大小 m。查找方法的返回值设计用自定义类返回父节点和下标是插入的关键前提定位插入位置。插入后的分裂检查插入后需立即判断usedSize m触发分裂逻辑。难点解析【难点】分裂的代码实现拆分原节点的关键字和子节点到左、右新节点中间关键字插入父节点后若父节点满需递归分裂关键字和子节点的移位操作保持有序性。多阶 B 树的通用性设计代码需支持任意 m 阶而非固定阶数。内容扩张Java 代码实现核心部分java运行import java.util.LinkedList; import java.util.Queue; /** * m阶B树此处取m3可修改常量支持任意阶 * 核心重点节点结构设计、查找逻辑、插入流程 * 核心难点分裂的递归实现、节点拆分与关键字移位 */ public class BTree { // 定义B树的阶数m阶每个节点最多有m个子节点 private static final int m 3; // 每个节点最多存储的关键字数量m-1 private static final int MAX_KEY m - 1; // 非根节点最少存储的关键字数量⌈m/2⌉ - 1m3时为1 private static final int MIN_KEY (m 1) / 2 - 1; // B树节点类【重点节点结构设计】 static class BTreeNode { int[] keys; // 关键字数组最多存储MAX_KEY个 BTreeNode[] children;// 孩子节点数组最多存储m个 BTreeNode parent; // 父节点引用 int usedSize; // 当前关键字数量 boolean isLeaf; // 是否为叶子节点 // 构造函数 public BTreeNode() { this.keys new int[MAX_KEY]; this.children new BTreeNode[m]; this.parent null; this.usedSize 0; this.isLeaf true; // 初始为叶子节点 } } // 查找结果类替代C的pair存储节点和下标 // 找到关键字node为目标节点index为关键字下标 // 未找到关键字node为父节点index为-1 static class SearchResult { BTreeNode node; int index; public SearchResult(BTreeNode node, int index) { this.node node; this.index index; } } private BTreeNode root; // B树的根节点 public BTree() { this.root null; } /** * 查找关键字 * 核心重点循环遍历节点内关键字定位子节点或目标关键字 * param key 要查找的关键字 * return 查找结果节点下标 */ private SearchResult search(int key) { BTreeNode curr root; BTreeNode parent null; while (curr ! null) { int i 0; // 找到第一个大于等于key的关键字下标 while (i curr.usedSize curr.keys[i] key) { parent curr; i; } // 找到关键字返回当前节点和下标 if (i curr.usedSize curr.keys[i] key) { return new SearchResult(curr, i); } // 未找到继续遍历子节点 parent curr; curr curr.children[i]; } // 未找到返回父节点和-1 return new SearchResult(parent, -1); } /** * 分裂节点处理满节点的拆分【核心难点递归分裂、节点拆分】 * param node 要分裂的节点此时节点的usedSize MAX_KEY 1即关键字数超上限 */ private void split(BTreeNode node) { // 1. 创建右节点左节点复用原节点 BTreeNode rightNode new BTreeNode(); BTreeNode parent node.parent; // 中间关键字的下标m3时mid1m为偶数时可调整为⌈m/2⌉ int mid MAX_KEY / 2; int midKey node.keys[mid]; // 2. 拆分原节点的关键字到右节点中间关键字右侧的关键字移到右节点 int j 0; for (int i mid 1; i node.usedSize; i) { rightNode.keys[j] node.keys[i]; rightNode.usedSize; node.usedSize--; j; } // 3. 拆分原节点的孩子节点到右节点非叶子节点时 if (!node.isLeaf) { j 0; for (int i mid 1; i m; i) { rightNode.children[j] node.children[i]; if (rightNode.children[j] ! null) { rightNode.children[j].parent rightNode; } node.children[i] null; // 原节点该位置置空 j; } } rightNode.isLeaf node.isLeaf; rightNode.parent parent; // 4. 中间关键字插入父节点 if (parent null) { // 父节点为空根节点分裂创建新根节点【难点根节点分裂处理】 BTreeNode newRoot new BTreeNode(); newRoot.keys[0] midKey; newRoot.usedSize 1; newRoot.isLeaf false; // 新根不是叶子节点 newRoot.children[0] node; newRoot.children[1] rightNode; node.parent newRoot; rightNode.parent newRoot; this.root newRoot; // 更新根节点 } else { // 父节点非空插入中间关键字到父节点【难点父节点插入后递归分裂】 // 找到插入位置 int i 0; while (i parent.usedSize parent.keys[i] midKey) { i; } // 关键字后移腾出插入位置保持有序性 for (int k parent.usedSize; k i; k--) { parent.keys[k] parent.keys[k - 1]; } // 孩子节点后移腾出位置 for (int k parent.usedSize 1; k i 1; k--) { parent.children[k] parent.children[k - 1]; } // 插入关键字和右孩子节点 parent.keys[i] midKey; parent.children[i 1] rightNode; parent.usedSize; // 检查父节点是否满满则递归分裂 if (parent.usedSize MAX_KEY) { split(parent); } } } /** * 插入关键字 * 核心重点叶子节点插入、插入后分裂检查 * param key 要插入的关键字 */ public void insert(int key) { // 情况1树为空创建根节点 if (root null) { root new BTreeNode(); root.keys[0] key; root.usedSize 1; return; } // 情况2树非空先查找关键字是否存在 SearchResult result search(key); if (result.index ! -1) { // 关键字已存在不插入 System.out.println(关键字 key 已存在不插入); return; } // 情况3关键字不存在定位到叶子节点插入 BTreeNode leaf result.node; int i 0; // 找到插入位置 while (i leaf.usedSize leaf.keys[i] key) { i; } // 关键字后移腾出插入位置 for (int k leaf.usedSize; k i; k--) { leaf.keys[k] leaf.keys[k - 1]; } // 插入关键字 leaf.keys[i] key; leaf.usedSize; // 检查是否需要分裂关键字数超过上限 if (leaf.usedSize MAX_KEY) { split(leaf); } } /** * 层序遍历打印B树辅助调试 */ public void print() { if (root null) { System.out.println(B树为空); return; } QueueBTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int levelSize queue.size(); for (int i 0; i levelSize; i) { BTreeNode curr queue.poll(); if (curr null) { continue; } // 打印当前节点的关键字 for (int j 0; j curr.usedSize; j) { System.out.print(curr.keys[j] ); } System.out.print(| ); // 将孩子节点加入队列 for (int j 0; j m; j) { if (curr.children[j] ! null) { queue.offer(curr.children[j]); } } } System.out.println(); // 换行表示下一层 } } // 测试代码 public static void main(String[] args) { BTree bTree new BTree(); // 插入测试序列 int[] keys {1, 3, 5, 7, 9, 11, 13}; for (int key : keys) { bTree.insert(key); } // 打印B树 System.out.println(B树层序遍历结果); bTree.print(); } }代码重难点标注节点类BTreeNodekeys和children数组的大小与 m 阶强关联keys为 m-1children为 m是多叉树的核心设计需严格匹配。查找方法search通过循环遍历节点内关键字定位子节点或目标关键字返回的SearchResult是插入逻辑的关键前提。分裂方法split中间关键字的选择mid MAX_KEY / 2是拆分节点的核心根节点分裂时的新根创建是树高增长的唯一场景父节点插入后的递归分裂是处理节点满的关键难点确保 B 树始终满足平衡特性。插入方法insert叶子节点的关键字移位插入是保持有序性的关键插入后的分裂检查是维持 B 树性质的核心步骤。