在學(xué)習(xí)MySql內(nèi)部機(jī)制過程中聋伦，了解到BTree和BTree+ 的原理夫偶，作為多年的程序員一時(shí)手癢難耐，決定自己也寫一個(gè)簡(jiǎn)易版的BTree 來自我提升嘉抓。

介紹不多講索守，反正網(wǎng)上一大堆，我是完全按照下圖的樹拆解流程圖來做：

BTree 圖解.gif

預(yù)錄入值：

const checked_list=[6,10,4,14,5,11,15,3,2,12,1,7,8,8,6,3,6,21,5,15,15,6,32,23,45,65,7,8,6,5,4];

代碼如下：

<script>
/*
key
value
parent_pointer
prev_pointer
next_pointer
sub_prev_pointer
sub_next_pointer
*/

//樹
let tree={};
//節(jié)點(diǎn)id抑片，自增
let node_auto_increment_id=new Date().getTime();
//定義一個(gè)葉子最大寬度
const NODE_WIDTH=3;

//測(cè)試校驗(yàn)生成的樹是否符合規(guī)則卵佛。
function toString(node,key=0,index=1,arrange=0,output=true){
    node=firstNode(node);
    let strings=[];
    while(node){
        strings.push(`父層：${key}：第${index}層的${arrange==0?"":(arrange==1?"左邊":"右邊")}的KEY為：${node.key}`);
        if(node.sub_prev_pointer){
            strings=strings.concat(toString(node.sub_prev_pointer,node.key,index+1,1,false));
        }

        if(node.sub_next_pointer){
            strings=strings.concat(toString(node.sub_next_pointer,node.key,index+1,2,false));
        }
        node=node.next_pointer;
    }
    if(output && strings.length>0){
//        console.log(`第${index}層的屬于KEY：${key}的${arrange==0?"":(arrange==1?"左邊":"右邊")}鍵值：${strings.join('，')}`);            
        let t=1;
        for(const str of strings){
            if(str.indexOf('左')>-1){
                console.warn(str+'           '+t);
            }
            else{
                console.log(str+'            '+t);
            }
            t++;
        }
    }
    if(!output)
        return strings;
}

//初始化
function init(num,value){
    tree=createNode(num,value);
}

//檢測(cè)當(dāng)前層的節(jié)點(diǎn)是否超出最大葉子寬度
function outOfNodeWidth(check_node){
    let width=1;
    let prev_pointer=check_node.prev_pointer;
    let next_pointer=check_node.next_pointer;
    while(prev_pointer){
        prev_pointer=prev_pointer.prev_pointer;
        width++;
    }
    while(next_pointer){
        next_pointer=next_pointer.next_pointer;
        width++;
    }
    return width>NODE_WIDTH;
}

//獲取當(dāng)前層第一個(gè)節(jié)點(diǎn)
function firstNode(check_node){
    while(true){
        if(!check_node.prev_pointer)break;
        check_node=check_node.prev_pointer;
    }
    return check_node;
}

//獲取當(dāng)前層指定位置的節(jié)點(diǎn)
function findLevelNode(check_node,index){
    check_node=firstNode(check_node);
    for(let i=0;i<index;i++){
        if(check_node.next_pointer)
            check_node=check_node.next_pointer;
        else
            break;
    }
    return check_node;
}

//創(chuàng)建一個(gè)新的臨時(shí)節(jié)點(diǎn)
function createNode(key,value){
    node_auto_increment_id++;
    return {
        id:node_auto_increment_id,
        key,
        value,
        prev_pointer:null,
        next_pointer:null,
        sub_prev_pointer:null,
        sub_next_pointer:null,
    };
}

//把新節(jié)點(diǎn)填充進(jìn)指定某層
function fillInLevel1Node(check_node,new_node){
    check_node=firstNode(check_node);
    //從第一個(gè)節(jié)點(diǎn)開始敞斋，去進(jìn)行插入截汪。
    let rt_node=check_node;
    //新節(jié)點(diǎn)居然已經(jīng)在同一層有出現(xiàn)
    
    while(rt_node){
        if(rt_node.id==new_node.id){
            return;
        }
        rt_node=rt_node.next_pointer;
    }

    rt_node=check_node;
    while(rt_node){
        if(rt_node.sub_next_pointer && rt_node.sub_next_pointer.id==new_node.id){
            rt_node.sub_next_pointer=null;
        }
        if(rt_node.sub_prev_pointer && rt_node.sub_prev_pointer.id==new_node.id){
            rt_node.sub_prev_pointer=null;
        }        
        rt_node=rt_node.next_pointer;
    }
    
    while(true){
        if(new_node.key<check_node.key){
            if(check_node.prev_pointer){
                check_node.prev_pointer.next_pointer=new_node;
            }
            new_node.prev_pointer=check_node.prev_pointer;
            new_node.next_pointer=check_node;
            check_node.prev_pointer=new_node;
            return;
        }
        if(check_node.next_pointer){
            check_node=check_node.next_pointer;
        }
        else{
            break;
        }
    }
    check_node.next_pointer=new_node;
    new_node.prev_pointer=check_node;

}

//添加節(jié)點(diǎn)，對(duì)外暴露的方法
function appendNode(new_key,value) {
    
    let new_node=createNode(new_key,value);
    let check_node=firstNode(tree);
    let parent_nodes=[];
    //找出符合的節(jié)點(diǎn)
    while(check_node){
        if(check_node.key<new_node.key){
            if((!check_node.next_pointer || check_node.next_pointer.key>=new_node.key) && check_node.sub_next_pointer){
                parent_nodes.push(check_node);
                check_node=check_node.sub_next_pointer;
            }
            else if(check_node.next_pointer){
                check_node=check_node.next_pointer;
            }
            else{
                break;
            }
        }
        else{
            if(check_node.sub_prev_pointer){
                parent_nodes.push(check_node);
                check_node=check_node.sub_prev_pointer;
            }
            else{
                break;
            }
        }
    }

    //把新節(jié)點(diǎn)插入到這個(gè)平層
    fillInLevel1Node(check_node,new_node);
    
    //如果當(dāng)前層的節(jié)點(diǎn)數(shù)已經(jīng)超過節(jié)點(diǎn)寬了植捎。
    //那么就需要把節(jié)點(diǎn)往上擺
    while(check_node){
        //如果平層節(jié)點(diǎn)沒有超出總值衙解，那么就可以跳出
        if(!outOfNodeWidth(check_node)){
            break;
        }
        const parent_node= parent_nodes.pop();
        //如果超出了，那就要擠出中間節(jié)點(diǎn)做父節(jié)點(diǎn)焰枢，然后一直往上檢查蚓峦。
        const pop_check=findLevelNode(check_node,Math.floor(NODE_WIDTH*0.5));
        if(pop_check.prev_pointer){
            pop_check.sub_prev_pointer=pop_check.prev_pointer;
            pop_check.prev_pointer.next_pointer=null;
            pop_check.prev_pointer=null;
        }
        if(pop_check.next_pointer){
            pop_check.sub_next_pointer=pop_check.next_pointer;
            pop_check.next_pointer.prev_pointer=null;
            pop_check.next_pointer=null;
        }

        //第一次拆分時(shí)是沒有根節(jié)點(diǎn)的舌剂，有根節(jié)點(diǎn)就代表屬于第二次拆分
        if(parent_node && parent_node.id!=pop_check.id){
            fillInLevel1Node(parent_node,pop_check);
            check_node=parent_node;
        }
        else if(!parent_node){
            tree=pop_check;
        }
    }
}

function searchNode(key,pos_node=null,debug=false){
    let check_node=pos_node;
    if(!check_node){
        check_node=firstNode(tree);
    }
    let link_count=0;
    let node_link_count=0;
    while(true){
        if(check_node.key==key && (pos_node==null || check_node!=pos_node)){
            if(debug)console.log(`一共進(jìn)行了${link_count}次指針移動(dòng)，${node_link_count}層下探暑椰。`);
            return check_node;
        }
        //如果KEY是小于當(dāng)前NODE的話,那就可能要往左下探霍转，
        if(key<check_node.key){
            if(!check_node.sub_prev_pointer){
                if(debug)console.log(`一共進(jìn)行了${link_count}次指針移動(dòng)，${node_link_count}層下探一汽。`);
                return null;
            }
            else{
                link_count++;
                node_link_count++;
                check_node=check_node.sub_prev_pointer;
                check_node=firstNode(check_node);
            }
        }
        //剩下就是大于當(dāng)前NODE的情況避消，
        else if(check_node.next_pointer){//如果有右層節(jié)點(diǎn)
            //如果小于右層節(jié)點(diǎn)，則需要往下探
            if(key<check_node.next_pointer.key){
                if(check_node.sub_next_pointer){
                    link_count++;
                    node_link_count++;
                    check_node=check_node.sub_next_pointer;
                    check_node=firstNode(check_node);
                }
                else{
                    if(debug)console.log(`一共進(jìn)行了${link_count}次指針移動(dòng)召夹，${node_link_count}層下探岩喷。`);
                    return null;
                }
            }
            else if(key>check_node.next_pointer.key){  //如果比右邊的node 還要大的話，則要繼續(xù)往右探
                link_count++;
                check_node=check_node.next_pointer;
            }
            else{
                if(debug)console.log(`一共進(jìn)行了${link_count}次指針移動(dòng)监憎，${node_link_count}層下探纱意。`);
                return check_node.next_pointer;
            }
        }
        //如果沒有右層節(jié)點(diǎn)，則檢查有沒有下層節(jié)點(diǎn)
        else if(check_node.sub_next_pointer){
            link_count++;
            node_link_count++;
            check_node=check_node.sub_next_pointer;
            check_node=firstNode(check_node);
        }
        //如果都沒有
        else{
            if(debug)console.log(`一共進(jìn)行了${link_count}次指針移動(dòng)枫虏，${node_link_count}層下探妇穴。`);
            return null;
        }
    }
    console.log(`一共進(jìn)行了${link_count}次指針移動(dòng)，${node_link_count}層下探隶债。`);
    return null;
}
</script>

按照?qǐng)D片腾它，編寫輸出結(jié)果：

const checked_list=[6,10,4,14,5,11,15,3,2,12,1,7,8,8,6,3,6,21,5,15,15,6,32,23,45,65,7,8,6,5,4];

let offset=0;

//然后一直插入新節(jié)點(diǎn)
for(const checked of checked_list){
    if(offset==0){
        init(checked,`val:${checked}：${offset}`);
    }
    else{
        appendNode(checked,`val:${checked}：${offset}`);
    }
    offset++;
}

//把樹的數(shù)據(jù)打印出來
//toString(tree);
//搜索某一個(gè)節(jié)點(diǎn)：例如21
//searchNode(21);

寫好后，也挺喜歡折騰一下自己死讹，驗(yàn)證使用了BTree后瞒滴，與普通的List 枚舉性能可以相差多大。生成10萬個(gè)隨機(jī)系數(shù)赞警，并且做好排序妓忍，進(jìn)行10萬次搜索，代碼如下：

console.log('配置初始化完成愧旦，開始進(jìn)行比較......');

let findAnwserCount=0;
let start_date=new Date().getTime();
for(let i=0;i<load_count;i++){
    let random=Math.floor(Math.random()*(load_count-1)+1);
    let key=start_id+random;
    
    if(searchNode(key,null,false)){
        findAnwserCount++;
    }
}
let end_date=new Date().getTime();

console.log(`通過使用BTree方式的搜索運(yùn)行完${load_count}次后世剖，找到的總數(shù)：${findAnwserCount}，總消耗時(shí)間：${(end_date-start_date)}毫秒`);


start_date=new Date().getTime();
findAnwserCount=0;
for(let i=0;i<load_count;i++){
    let random=Math.floor(Math.random()*(load_count-1)+1);
    let key=start_id+random;
    for(const item of listItem){
        if(item.key==key){
            findAnwserCount++;
            break;
        }
    }    
}
end_date=new Date().getTime();

console.log(`通過使用List方式的搜索運(yùn)行完${load_count}次后笤虫，找到的總數(shù)：${findAnwserCount}旁瘫，總消耗時(shí)間：${(end_date-start_date)}毫秒`);

最后輸出結(jié)果：

所有配置準(zhǔn)備初始化......
配置初始化完成，開始進(jìn)行比較......

通過使用BTree方式的搜索運(yùn)行完100000次后琼蚯，找到的總數(shù)：100000酬凳，總消耗時(shí)間：33毫秒

通過使用List方式的搜索運(yùn)行完100000次后，找到的總數(shù)：100000遭庶，總消耗時(shí)間：5734毫秒