B - 트 리 B + 트 리 정의 와 간단 한 조작

B - 트 리 B + 트 리 정의 와 간단 한 조작
  • B - 나무의 정의 노드 의 아이 노드 의 최대 수 는 단계 용 m 로 모든 잎 노드 가 같은 층 에 있 음 을 나타 내 고 정 보 를 가지 지 않 으 며 각 노드 에 최대 m 개의 서브 트 리 가 포함 되 어 있다.최대 m - 1 개의 관건 적 인 자근 노드 를 포함 하 는 것 은 터미널 노드 가 아 닙 니 다. 그러면 뿌리 노드 는 적어도 두 개의 나무 가 뿌리 노드 를 제외 한 다른 비 잎 노드 는 적어도 m / 2 가 있 습 니 다. 키 트 리 의 모든 비 잎 노드 의 구 조 는 n, p0, k1, p1, k2, p2, k3, p3. kn 입 니 다. pn 중 n 은 키워드 의 개수 m / 2 - 1 키 워드 는 ki 가 ki + 1 보다 작고 pn 이 가리 키 는 키 워드 는 kn
  • 보다 큽 니 다.
    /**
     * @Author JH
     * @CreateDate 18-5-31
     * @Description B-   
     */
    class Node{
        int num;
        int []key;
        Node parent;
        Node []child;
    
        public Node(int m) {
            this.key = new int[m];
            this.child =new Node[m];
        }
    
        public Node(int num, int[] key, Node parent, Node[] child) {
            this.num = num;
            this.key = key;
            this.parent = parent;
            this.child = child;
        }
    }
    class Result{
        Node r;
        int i;
        int tag;
    }
    public class B_Tree {
        public Result B_TreeSearch(Node root,int k){
            Node p=root;
            Node q=null;
            Result r=new Result();
            int i=0;
            boolean find=false;
            while (p!=null&&!find){//    k  p   
                i=search(root,k);//  k   
                if (k==p.key[i]&&find==false){
                    find=true;
                }else{//q  k       
                    q=p;
                    p=p.child[i];
                }
            }
            r.i=i;
            if (find){
               r.r=p;//          
               r.tag=1;
            }else{//       k          
                r.r=q;
                r.tag=0;
            }return r;
        }
        public  int search (Node root,int k){
            int i=0;//     k root           key[i]<k<key[i+1]
            for(;i<root.num&&root.key[i+1]<=k;i++);
            return i;
        }
    }
    
  • m 단계 B + 나 무 는 모든 가지 에 m 그루 의 나무 뿌리 노드 가 자나무 가 없 거나 적어도 두 개의 뿌리 노드 를 제외 한 다른 노드 가 적어도 m / 2 위로 전체 나 무 를 추출 하고 n 그루 의 나무 가 있 는 노드 는 n 개의 키워드 잎 노드 가 모든 키 워드 를 포함 하고 해당 하 는 기록 만 을 원 하 는 지침 이 있 으 며 잎 노드 는 키워드 크기 순서에 따라 연결된다.(모든 잎 노드 는 기본 색인 블록 으로 볼 수 있 습 니 다. 포인터 가 데이터 파일 의 기록 을 가리 키 고 있 습 니 다) 모든 분기 노드 (색인 으로 볼 수 있 는 색인) 에는 그의 각 키 노드 의 최대 키워드 와 하위 노드 를 가리 키 는 지침
  • 만 포함 되 어 있 습 니 다.

    좋은 웹페이지 즐겨찾기