在学习MySql内部机制过程中，了解到BTree和BTree+ 的原理，作为多年的程序员一时手痒难耐，决定自己也写一个简易版的BTree 来自我提升。
介绍不多讲，反正网上一大堆，我是完全按照下图的树拆解流程图来做：
BTree 图解.gif
预录入值：
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={};
//节点id，自增
let node_auto_increment_id=new Date().getTime();
//定义一个叶子最大宽度
const NODE_WIDTH=3;
//测试校验生成的树是否符合规则。
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);
}
//检测当前层的节点是否超出最大叶子宽度
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;
}
//获取当前层第一个节点
function firstNode(check_node){
while(true){
if(!check_node.prev_pointer)break;
check_node=check_node.prev_pointer;
}
return check_node;
}
//获取当前层指定位置的节点
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;
}
//创建一个新的临时节点
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,
};
}
//把新节点填充进指定某层
function fillInLevel1Node(check_node,new_node){
check_node=firstNode(check_node);
//从第一个节点开始，去进行插入。
let rt_node=check_node;
//新节点居然已经在同一层有出现
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;
}
//添加节点，对外暴露的方法
function appendNode(new_key,value) {
let new_node=createNode(new_key,value);
let check_node=firstNode(tree);
let parent_nodes=[];
//找出符合的节点
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;
}
}
}
//把新节点插入到这个平层
fillInLevel1Node(check_node,new_node);
//如果当前层的节点数已经超过节点宽了。
//那么就需要把节点往上摆
while(check_node){
//如果平层节点没有超出总值，那么就可以跳出
if(!outOfNodeWidth(check_node)){
break;
}
const parent_node= parent_nodes.pop();
//如果超出了，那就要挤出中间节点做父节点，然后一直往上检查。
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;
}
//第一次拆分时是没有根节点的，有根节点就代表属于第二次拆分
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(`一共进行了${link_count}次指针移动，${node_link_count}层下探。`);
return check_node;
}
//如果KEY是小于当前NODE的话,那就可能要往左下探，
if(key<check_node.key){
if(!check_node.sub_prev_pointer){
if(debug)console.log(`一共进行了${link_count}次指针移动，${node_link_count}层下探。`);
return null;
}
else{
link_count++;
node_link_count++;
check_node=check_node.sub_prev_pointer;
check_node=firstNode(check_node);
}
}
//剩下就是大于当前NODE的情况，
else if(check_node.next_pointer){//如果有右层节点
//如果小于右层节点，则需要往下探
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(`一共进行了${link_count}次指针移动，${node_link_count}层下探。`);
return null;
}
}
else if(key>check_node.next_pointer.key){ //如果比右边的node 还要大的话，则要继续往右探
link_count++;
check_node=check_node.next_pointer;
}
else{
if(debug)console.log(`一共进行了${link_count}次指针移动，${node_link_count}层下探。`);
return check_node.next_pointer;
}
}
//如果没有右层节点，则检查有没有下层节点
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(`一共进行了${link_count}次指针移动，${node_link_count}层下探。`);
return null;
}
}
console.log(`一共进行了${link_count}次指针移动，${node_link_count}层下探。`);
return null;
}
</script>
按照图片，编写输出结果：
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;
//然后一直插入新节点
for(const checked of checked_list){
if(offset==0){
init(checked,`val:${checked}：${offset}`);
}
else{
appendNode(checked,`val:${checked}：${offset}`);
}
offset++;
}
//把树的数据打印出来
//toString(tree);
//搜索某一个节点：例如21
//searchNode(21);
写好后，也挺喜欢折腾一下自己，验证使用了BTree后，与普通的List 枚举性能可以相差多大。生成10万个随机系数，并且做好排序，进行10万次搜索，代码如下：
console.log('配置初始化完成，开始进行比较......');
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方式的搜索运行完${load_count}次后，找到的总数：${findAnwserCount}，总消耗时间：${(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方式的搜索运行完${load_count}次后，找到的总数：${findAnwserCount}，总消耗时间：${(end_date-start_date)}毫秒`);
最后输出结果：
所有配置准备初始化......
配置初始化完成，开始进行比较......
通过使用BTree方式的搜索运行完100000次后，找到的总数：100000，总消耗时间：33毫秒
通过使用List方式的搜索运行完100000次后，找到的总数：100000，总消耗时间：5734毫秒
