查找-多路查找详解篇2

B+树（B+ tree）是B-树的一种变种，特别适用于范围查询和顺序访问。

B+树与B-树类似，由节点组成，每个节点可以存储多个关键字，这些关键字按升
序排列。
B+树的特点是只有叶子节点存储了真实数据，而内部节点仅用于索引。叶子节点
通过指针连接形成一个链表，方便范围查询和顺序访问。

内部节点存储关键字和指向子节点的指针。
内部节点的关键字按升序排列，用于指示范围查询的起点。
内部节点的指针指向比关键字更大的子节点。

叶子节点存储真实数据和指向下一个叶子节点的指针。
叶子节点的关键字按升序排列，支持范围查询和顺序访问。
所有叶子节点通过指针连接成一个链表，便于范围查询和顺序访问。

当要插入一个关键字时，从根节点开始，找到合适的叶子节点。
如果叶子节点已满，则需要进行节点分裂操作。将中间位置的关键字提升到父节
点，并将两个剩余的部分分别创建为新的叶子节点。
如果叶子节点还没有满，则直接将关键字插入到合适的位置。

当要删除一个关键字时，从根节点开始，找到包含该关键字的叶子节点。
直接删除叶子节点中的关键字，并更新链表指针。
删除操作后，如果叶子节点的关键字个数过少，则需要从兄弟节点借用关键字或
进行节点合并。

B+树的查询操作与B-树类似，从根节点开始，根据关键字的大小比较，向左或向
  右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。
对于范围查询和顺序访问，可以从叶子节点开始，沿着链表进行遍历。

B+树的特点在于只有叶子节点存储真实数据，这样使得范围查询和顺序访问更加
高效，因为数据在叶子节点上连续存储，读取连续的数据块比随机读取更快。而
内部节点仅存储索引信息，可以容纳更多的索引，提高了查询效率。B+树的实现
适用于需要高效地处理大量数据的数据库和文件系统，能够提供较高的查询性能
和存储效率。

import java.util.ArrayList;
import java.util.List;
class BPlusTreeNode {
    public boolean isLeaf;
    public List<Integer> keys;
    public List<Object> values;
    public List<BPlusTreeNode> children;
    public BPlusTreeNode next;
    public BPlusTreeNode() {
        isLeaf = false;
        keys = new ArrayList<>();
        values = new ArrayList<>();
        children = new ArrayList<>();
        next = null;
    }
}
class BPlusTree {
    private BPlusTreeNode root;
    private int m;
    public BPlusTree(int m) {
        root = new BPlusTreeNode();
        root.isLeaf = true;
        this.m = m;
    }
    // 插入操作
    public void insert(int key, Object value) {
        if (root.keys.size() == m) {
            BPlusTreeNode newRoot = new BPlusTreeNode();
            newRoot.children.add(root);
            splitChild(newRoot, 0, root);
            root = newRoot;
        }
        insertNonFull(root, key, value);
    }
    // 非满子节点插入操作
    private void insertNonFull(BPlusTreeNode node, int key, Object value) {
        int index = node.keys.size() - 1;
        if (node.isLeaf) {
            while (index >= 0 && node.keys.get(index) > key) {
                index--;
            }
            node.keys.add(index + 1, key);
            node.values.add(index + 1, value);
            node.next = node.next;
        } else {
            while (index >= 0 && node.keys.get(index) > key) {
                index--;
            }
            index++;
            if (node.children.get(index).keys.size() == m) {
                splitChild(node, index, node.children.get(index));
                if (node.keys.get(index) < key) {
                    index++;
                }
            }
            insertNonFull(node.children.get(index), key, value);
        }
    }
    // 分裂满子节点
    private void splitChild(BPlusTreeNode parent, int index, BPlusTreeNode node) {
        BPlusTreeNode newNode = new BPlusTreeNode();
        newNode.isLeaf = node.isLeaf;
        parent.keys.add(index, node.keys.get(m / 2));
        parent.children.add(index + 1, newNode);
        newNode.keys.addAll(node.keys.subList((m / 2) + 1, m));
        newNode.values.addAll(node.values.subList((m / 2) + 1, m));
        if (!node.isLeaf) {
            newNode.children.addAll(node.children.subList((m / 2) + 1, m + 1));
            node.children.subList((m / 2) + 1, m + 1).clear();
        } else {
            newNode.next = node.next;
            node.next = newNode;
        }
        node.keys.subList(m / 2, m).clear();
        node.values.subList(m / 2, m).clear();
    }
    // 搜索操作
    public List<Object> search(int key) {
        return search(root, key);
    }
    private List<Object> search(BPlusTreeNode node, int key) {
        int index = 0;
        while (index < node.keys.size() && key > node.keys.get(index)) {
            index++;
        }
        if (index < node.keys.size() && key == node.keys.get(index)) {
            return node.values.get(index);
        } else if (node.isLeaf) {
            return null;
        } else {
            return search(node.children.get(index), key);
        }
    }
}

B树（B-tree）是一种平衡的多路查找树，主要用于在磁盘等外部存储设备中高
效地存储和检索大量数据。以下是关于B树的详细介绍：

B树由节点组成，每个节点可以存储多个关键字，这些关键字按升序排列。
B树的特点是节点的关键字按升序排列，具有高度平衡的特性。
每个节点通常有多个子节点，最多可以拥有m个子节点，其中m称为B树的阶数。

当要插入一个关键字时，从根节点开始，判断关键字应插入的位置。
如果节点已满（即已有m-1个关键字），则需要进行节点分裂操作。将中间位置
的关键字提升为父节点，并将节点分裂为两个节点，将剩余的关键字均匀分配到
这两个节点中。
如果要插入的节点还没有满，则直接将关键字插入到合适的位置。

当要删除一个关键字时，从根节点开始，找到包含该关键字的节点。
如果该节点是叶子节点，直接删除关键字。
如果该节点是内部节点，有几种情况需要处理：
如果该节点有足够多的关键字，则可以直接删除关键字。
如果该节点的关键字数量过少，需要考虑兄弟节点的关键字数量以及兄弟节点合
并的情况。

B树的查询操作与二叉查找树类似，从根节点开始，根据关键字的大小比较，向
左或向右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。
B树适用于大规模数据存储和查询的场景，特别适用于外部存储设备上的数据存
储。其平衡性保证了较为均衡的查询性能，因为从根节点到叶子节点的路径长度
相等或差别不大。B树的阶数m可以根据具体应用和硬件限制来选择，较大的阶数
有助于减少磁盘访问的次数，提高效率。

B树的变种B+树在B树的基础上做了一些优化，将所有的数据都存储在叶子节点
中，使得范围查询和顺序访问更加高效。因此，B+树在现代数据库系统和文件
系统中更为常见和广泛应用。、

import java.util.ArrayList;
import java.util.List;
class BTreeNode {
    int degree; // B树的阶数
    List<Integer> keys; // 节点中存储的关键字
    List<BTreeNode> children; // 节点的子节点
    boolean isLeaf; // 是否是叶子节点
    public BTreeNode(int degree, boolean isLeaf) {
        this.degree = degree;
        this.isLeaf = isLeaf;
        keys = new ArrayList<>();
        children = new ArrayList<>();
    }
}
class BTree {
    BTreeNode root; // B树的根节点
    int degree; // B树的阶数
    public BTree(int degree) {
        this.degree = degree;
        root = new BTreeNode(degree, true);
    }
    // 插入关键字
    public void insert(int key) {
        if (root.keys.size() == (2 * degree - 1)) {
            BTreeNode newRoot = new BTreeNode(degree, false);
            newRoot.children.add(root);
            splitChild(newRoot, 0, root);
            root = newRoot;
        }
        insertNonFull(root, key);
    }
    // 在非满节点插入关键字
    private void insertNonFull(BTreeNode node, int key) {
        int index = node.keys.size() - 1;
        if (node.isLeaf) {
            while (index >= 0 && key < node.keys.get(index)) {
                index--;
            }
            node.keys.add(index + 1, key);
        } else {
            while (index >= 0 && key < node.keys.get(index)) {
                index--;
            }
            index++;
            if (node.children.get(index).keys.size() == (2 * degree - 1)) {
                splitChild(node, index, node.children.get(index));
                if (key > node.keys.get(index)) {
                    index++;
                }
            }
            insertNonFull(node.children.get(index), key);
        }
    }
    // 分裂子节点
    private void splitChild(BTreeNode parent, int index, BTreeNode node) {
        BTreeNode newNode = new BTreeNode(degree, node.isLeaf);
        parent.keys.add(index, node.keys.get(degree - 1));
        parent.children.add(index + 1, newNode);
        for (int i = 0; i < degree - 1; i++) {
            newNode.keys.add(node.keys.get(i + degree));
            if (!node.isLeaf) {
                newNode.children.add(node.children.get(i + degree));
            }
        }
        if (!node.isLeaf) {
            newNode.children.add(node.children.get(2 * degree - 1));
        }
        for (int i = degree - 1; i >= 0; i--) {
            node.keys.remove(i + degree - 1);
            if (!node.isLeaf) {
                node.children.remove(i + degree);
            }
        }
    }
    // 搜索关键字
    public boolean search(int key) {
        return search(root, key);
    }
    private boolean search(BTreeNode node, int key) {
        int index = 0;
        while (index < node.keys.size() && key > node.keys.get(index)) {
            index++;
        }
        if (index < node.keys.size() && key == node.keys.get(index)) {
            return true;
        } else if (node.isLeaf) {
            return false;
        } else {
            return search(node.children.get(index), key);
        }
    }
}

Trie树，也被称为字典树或前缀树，是一种用于高效存储和搜索字符串的树型数
据结构。Trie树的主要特点是通过字符串的前缀来进行搜索和匹配。

Trie树由根节点和一系列子节点组成。
根节点不包含任何关键字，每个子节点都表示一个字符，并按字符的顺序连接形
成路径。
从根节点到每个叶子节点的路径都对应一个字符串。
每个节点可以存储额外的信息，如词频或附加数据等。

当要插入一个字符串时，从根节点开始，逐个字符按顺序插入。
如果某个字符对应的子节点不存在，则创建一个新的子节点。
插入字符串的最后一个字符后，将当前节点标记为一个单词的结束。

当要搜索一个字符串时，从根节点开始，逐个字符按顺序匹配。
如果某个字符对应的子节点存在，则继续匹配下一个字符。
如果匹配遇到缺失的字符或到达某个节点后没有子节点，则表示字符串不在Trie
树中。
如果匹配成功并且在Trie树中找到最后一个字符，则表示字符串存在于Trie树中。

当要删除一个字符串时，从根节点开始，逐个字符按顺序遍历。
如果遍历过程中发现某个字符对应的子节点不存在，则表示字符串不存在于Trie
树中。
如果遍历成功，并到达字符串的最后一个字符，将当前节点的结束标记取消。
如果遍历成功，但还存在其他相关字符串（例如，删除"abc"但还有"abcd"），
可以保留当前节点以表示其他相关字符串。

搜索的时间复杂度与字符串长度无关，仅与Trie树的高度相关，通常比哈希表更
高效。
可以高效地搜索具有相同前缀的字符串集合。
对于字符串的前缀匹配和自动补全，Trie树可以提供高效的结果。

空间消耗较大，尤其在处理大量长字符串时。为了缓解这个问题，可以使用压缩
的Trie树，如压缩前缀树（Patricia树）或Trie树的变种来减少存储空间。

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;
    public TrieNode() {
        children = new TrieNode[26]; // 26个英文字母
        isEndOfWord = false;
    }
    public TrieNode getChild(char ch) {
        return children[ch - 'a'];
    }
    public void setChild(char ch, TrieNode node) {
        children[ch - 'a'] = node;
    }
    public boolean isEndOfWord() {
        return isEndOfWord;
    }
    public void setEndOfWord(boolean isEndOfWord) {
        this.isEndOfWord = isEndOfWord;
    }
}
class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.getChild(ch) == null) {
                node.setChild(ch, new TrieNode());
            }
            node = node.getChild(ch);
        }
        node.setEndOfWord(true);
    }
    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord();
    }
    public boolean startsWith(String prefix) {
        TrieNode node = findNode(prefix);
        return node != null;
    }
    private TrieNode findNode(String str) {
        TrieNode node = root;
        for (char ch : str.toCharArray()) {
            node = node.getChild(ch);
            if (node == null) {
                return null;
            }
        }
        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("banana");
        trie.insert("grape");
        System.out.println(trie.search("apple")); // 输出: true
        System.out.println(trie.search("orange")); // 输出: false
        System.out.println(trie.startsWith("app")); // 输出: true
        System.out.println(trie.startsWith("ban")); // 输出: true
        System.out.println(trie.startsWith("grap")); // 输出: true
    }
}