정의

컴퓨터 과학에서, B 트리(영어: B-tree)는 자동 균형을 유지하는 트리로, 데이터를 정렬할 수 있습니다. 이 데이터 구조는 데이터를 검색하고, 순차적으로 접근하고, 데이터를 삽입하고, 데이터를 삭제하는 작업을 대수 시간 내에 완료할 수 있습니다.

B 트리를 도입하는 이유는 무엇인가요?63;

먼저, 우리가 이전에 소개한 레드-블랙 트리는 입력을메모리의 하나내부 검색 트리。

B 트리는 이전의 균형 트리 알고리즘의 확장으로, 저장된디스크나 네트워크의 시ンボル 테이블에서외부 검색이 파일들은 우리가 이전에 고려한 입력보다 훨씬 크게 될 수 있습니다(메모리에 저장하기 어려울 수 있습니다).

내용이 디스크에 저장되어 있기 때문에, 트리의 깊이가 너무 깊어 디스크 I/O 읽기와 쓰기가 너무 자주 일어나면(디스크 읽기와 쓰기 속도는 제한적입니다)，그로 인해 쿼리 효율성이 낮아집니다。

그래서 트리의 깊이를 줄이는 것은 자연스럽게 중요합니다. 따라서 우리는 B 트리를 도입했습니다. 다중 경로 검색 트리。

특징

트리의 각 노드는 최대 m개의 자식을 가질 수 있습니다（m>=2）；

루트 노드와 리브러리 노드를 제외하고, 다른 각 노드는 최소한 [ceil(m / 2자식 노드가 있습니다（where ceil(x) is a ceiling function）；

루트 노드가 리브러리 노드가 아니면 최소한2자식 노드가 있습니다（특수 경우：자식 노드가 없는 루트 노드, 즉 루트 노드가 리브러리 노드이고, 나무에 루트 노드가 하나만 있습니다）；

모든 리브러리 노드는 같은 층에 나타납니다(최하층),리브러리 노드는 외부 노드로, 내용을 저장하며, 즉 key와 value。

기타 노드는 내부 노드로, 인덱스를 저장하며, 즉 key와 next。

내부 노드의 키 key：K[1], K[2], …, K[M-1]；그리고 K[i] < K[i+1]；

내용 노드의 포인터 next：P[1], P[2], …, P[M]；그리고 P[1], K[1], K[i]의 자식 트리에 대해 P[M]는 키가 K[M-1], K[i]의 자식 트리에 대해 다른 P[i]는 키가 K[i-1], K[i])의 자식 트리；

예를 들어：（M=3)

검색과 삽입

편리를 위해 특별한 기호 키를 사용했으며, 이 키는 다른 모든 키보다 작습니다.*표시

처음에는 B 트리가 단 하나의 루트 노드만 있으며, 이 루트 노드는 초기화 시에만 기호 키를 포함합니다.

내부 노드의 각 키는 노드와 연결되어 있으며, 이 노드를 루트로 하는 자식 트리에서 모든 키는 이 노드와 연결된 키보다 크거나 같지만, 다른 모든 키보다 작습니다.

이러한 약정은 대부분 코드를 간소화할 수 있습니다.

코드

다운로드하기 클릭

이 코드는 기호 키를 도입했지만, 코드 출력은 그것을 제거했습니다.

코드에 기호 키가 포함된 B 트리（이미지를 로컬로 저장하여 확인하세요，문자가 더 명확합니다）：

코드가 출력한 B 트리（이미지를 로컬로 저장하여 확인하세요，문자가 더 명확합니다）：

public class BTree<Key extends Comparable<Key>, Value> 
{
  // B 별 최대 자식 수-트리 노드 = M-1
  // (짝수이고 더 크어야 합니다) 2)
  private static final int M = 4;
  private Node root;    // B의 루트-tree
  private int height;   // B의 높이-tree
  private int n;      // ключ 수-B에 있는 값 쌍-tree
  // 헬퍼 B-트리 노드 데이터 타입
  private static final class Node 
  {
    private int m;               // number of children
    private Entry[] children = new Entry[M];  // the array of children
    // create a node with k children
    private Node(int k) 
    {
      m = k;
    }
  }
  // internal nodes: only use key and next
  // external nodes: only use key and value
  private static class Entry 
  {
    private Comparable key;
    private Object val;
    private Node next;   // helper field to iterate over array entries
    public Entry(Comparable key, Object val, Node next) 
    {
      this.key = key;
      this.val = val;
      this.next = next;
    }
  }
  /**
   * Initializes an empty B-tree.
   */
  public BTree() 
  {
    root = new Node(0);
  }
  /**
   * Returns true if this symbol table is empty.
   * @return {@code true} if this symbol table is empty; {@code false} otherwise
   */
  public boolean isEmpty() 
  {
    return size() == 0;
  }
  /**
   * Returns the number of key-value pairs in this symbol table.
   * @return the number of key-value pairs in this symbol table
   */
  public int size() 
  {
    return n;
  }
  /**
   * Returns the height of this B-tree (for debugging).
   *
   * @return the height of this B-tree
   */
  public int height() 
  {
    return height;
  }
  /**
   * 주어진 키와 관련된 값을 반환합니다.
   *
   * @param 키 키
   * @return 키가 기호 테이블에 있으면 해당 키와 관련된 값을 반환
   *     키가 기호 테이블에 없으면 null
   * @throws NullPointerException 키가 null이면
   */
  public Value get(Key 키) 
  {
    if (키 == null) 
    {
      throw new NullPointerException("key must not be null");
    }
    return search(root, 키, height);
  }
  @SuppressWarnings("unchecked")
  private Value search(Node x, Key 키, int ht) 
  {
    Entry[] children = x.children;
    // external node에서 가장 하위의 leaf 노드까지 순회
    if (ht == 0) 
    {
      for (int j = 0; j < x.m; j++)       
      {
        if (eq(키, children[j].키)) 
        {
          return (Value) children[j].val;
        }
      }
    }
    // internal node로의 재귀적인 next 주소 검색
    else 
    {
      for (int j = 0; j < x.m; j++) 
      {
        if (j+1 == x.m || less(키, children[j+1].key))
        {
          return search(children[j].next, 키, ht-1);
        }
      }
    }
    return null;
  }
  /**
   * 키를 삽입합니다-값 쌍을 기호 테이블에 삽입하여 기존 값을 덮어쓰습니다.
   * 키가 기호 테이블에 이미 존재하면 새로운 값으로 대체합니다.
   * 값이 null이면, 이는 키를 기호 테이블에서 실질적으로 제거하는 것입니다.
   *
   * @param 키 키
   * @param 값 값
   * @throws NullPointerException 키가 null이면
   */
  public void put(Key 키, Value 값) 
  {
    if (키 == null) 
    {
      throw new NullPointerException("key must not be null");
    }
    Node u = insert(root, key, val, height); //분할 후 생성된 오른쪽 노드
    n++;
    if (u == null) 
    {
      return;
    }
    // root를 재조직해야 합니다
    Node t = new Node(2);
    t.children[0] = new Entry(root.children[0].key, null, root);
    t.children[1] = new Entry(u.children[0].key, null, u);
    root = t;
    height++;
  }
  private Node insert(Node h, Key key, Value val, int ht) 
  {
    int j;
    Entry t = new Entry(key, val, null);
    // external node 외부 노드, 또한 잎 노드이며, 트리의 가장 하단에 위치하며, 저장되는 것은 내용 값
    if (ht == 0) 
    {
      for (j = 0; j < h.m; j++) 
      {
        if (less(key, h.children[j].key)) 
        {
          break;
        }
      }
    }
    // internal node 내부 노드, 저장되는 것은 next 주소
    else 
    {
      for (j = 0; j < h.m; j++) 
      {
        if ((j+1 == h.m) || less(key, h.children[j+1].key)) 
        {
          Node u = insert(h.children[j++].next, key, val, ht-1);
          if (u == null) 
          {
            return null;
          }
          t.key = u.children[0].key;
          t.next = u;
          break;
        }
      }
    }
    for (int i = h.m; i > j; i--)
    {
      h.children[i] = h.children[i-1);
    }
    h.children[j] = t;
    h.m++;
    if (h.m < M) 
    {
      return null;
    }
    else     
    {  //분할 점
      return split(h);
    }
  }
  // split node in half
  private Node split(Node h) 
  {
    Node t = new Node(M/2);
    h.m = M/2;
    for (int j = 0; j < M/2; j++)
    {
      t.children[j] = h.children[M/2+j];     
    }
    return t;  
  }
  /**
   * Returns a string representation of this B-tree (for debugging).
   *
   * @return a string representation of this B-tree.
   */
  public String toString() 
  {
    return toString(root, height, "") + "\n";
  }
  private String toString(Node h, int ht, String indent) 
  {
    StringBuilder s = new StringBuilder();
    Entry[] children = h.children;
    if (ht == 0) 
    {
      for (int j = 0; j < h.m; j++) 
      {
        s.append(indent + children[j].key + " " + children[j].val + "\n");
      }
    }
    else 
    {
      for (int j = 0; j < h.m; j++) 
      {
        if (j > 0) 
        {
          s.append(indent + "(" + children[j].key + ")\n");
        }
        s.append(toString(children[j].next, ht-1, indent + "   "));
      }
    }
    return s.toString();
  }
  // comparison functions - make Comparable instead of Key to avoid casts
  private boolean less(Comparable k1, Comparable k2) 
  {
    return k1.compareTo(k2) < 0;
  }
  private boolean eq(Comparable k1, Comparable k2) 
  {
    return k1.compareTo(k2) == 0;
  }
  /**
   * Unit tests the {@code BTree} data type.
   *
   * @param args the command-line arguments
   */
  public static void main(String[] args) 
  {
    BTree<String, String> st = new BTree<String, String>();
    st.put("www.cs.princeton.edu", "128.112.136.12
    st.put("www.cs.princeton.edu", "128.112.136.11
    st.put("www.princeton.edu", "128.112.128.15
    st.put("www.yale.edu", ")130.132.143.21
    st.put("www.simpsons.com", ");209.052.165.60);
    st.put("www.apple.com", ");17.112.152.32
    st.put("www.amazon.com", ");207.171.182.16
    st.put("www.ebay.com", ");66.135.192.87
    st.put("www.cnn.com", ");64.236.16.20);
    st.put("www.google.com", ");216.239.41.99
    st.put("www.nytimes.com", ");199.239.136.200);
    st.put("www.microsoft.com", ");207.126.99.140);
    st.put("www.dell.com", ");143.166.224.230);
    st.put("www.slashdot.org", ");66.35.250.151
    st.put("www.espn.com", ");199.181.135.201
    st.put("www.weather.com", ");63.111.66.11
    st.put("www.yahoo.com", ");216.109.118.65
    System.out.println("cs.princeton.edu: "); + st.get("www.cs.princeton.edu"));
    System.out.println("hardvardsucks.com: "); + st.get("www.harvardsucks.com"));
    System.out.println("simpsons.com: "); + st.get("www.simpsons.com"));
    System.out.println("apple.com: "); + st.get("www.apple.com"));
    System.out.println("ebay.com: "); + st.get("www.ebay.com"));
    System.out.println("dell.com: "); + st.get("www.dell.com"));
    System.out.println();
    System.out.println("size: "); + st.size());
    System.out.println("height: "); + st.height());
    System.out.println(st);
    System.out.println();
  }
}

출력:
cs.princeton.edu:　 128.112.136.12
hardvardsucks.com: null
simpsons.com:　　　　　 209.052.165.60
apple.com:　　　　　　　　 17.112.152.32
ebay.com:　　　　　　　　　 66.135.192.87
dell.com:　　　　　　　　　 143.166.224.230

size:　　　 17
height:　 2
　　　　　　　　　 www.amazon.com 207.171.182.16
　　　　　　　　　 www.apple.com 17.112.152.32
　　　　　　　　　 www.cnn.com 64.236.16.20
　　　　 (www.cs.princeton.edu)
　　　　　　　　　 www.cs.princeton.edu 128.112.136.12
　　　　　　　　　 www.cs.princeton.edu 128.112.136.11
　　　　　　　　　 www.dell.com 143.166.224.230
(www.ebay.com)
　　　　　　　　　 www.ebay.com 66.135.192.87
　　　　　　　　　 www.espn.com 199.181.135.201
　　　　　　　　　 www.google.com 216.239.41.99
　　　　 (www.microsoft.com)
　　　　　　　　　 www.microsoft.com 207.126.99.140
　　　　　　　　　 www.nytimes.com 199.239.136.200
(www.princeton.edu)
　　　　　　　　　 www.princeton.edu 128.112.128.15
　　　　　　　　　 www.simpsons.com 209.052.165.60
　　　　 (www.slashdot.org)
　　　　　　　　　 www.slashdot.org 66.35.250.151
　　　　　　　　　 www.weather.com 63.111.66.11
　　　　 (www.yahoo.com)
　　　　　　　　　 www.yahoo.com 216.109.118.65
　　　　　　　　　 www.yale.edu 130.132.143.21

이것이 이 문서의 전체 내용입니다. 많은 도움이 되었기를 바랍니다. 또한,呐喊 교본에 많은 지원을 부탁드립니다.

선언: 이 문서의 내용은 인터넷에서 가져왔으며, 저작권자는 모두가 소유합니다. 내용은 인터넷 사용자가 자발적으로 기여하고 업로드한 것이며, 이 사이트는 소유권을 가지지 않으며, 인공적인 편집을 하지 않았으며, 관련 법적 책임도 부담하지 않습니다. 저작권 위반이 의심되는 내용이 있다면, notice#w로 이메일을 보내 주세요.3codebox.com（메일을 보내면, #을 @으로 바꿔서 보내시고, 관련 증거를 제공해 주세요. 사실이 확인되면, 이 사이트는 즉시 위반 내용을 삭제합니다.）