自己实现基于key-value的NoSQL数据库（三）—— B+树和Hash算法

前一篇文章中，效率成了很关键的问题，比较数据库还是需要能高效查找数据才行

那么如何解决查找问题呢？一个很好的办法是使用B+树，关于B+树就不做多的介绍了，网上有很多

这里只贴出定义

B-树
       是一种多路搜索树（并不是二叉的）：
       .定义任意非叶子结点最多只有M个儿子；且M；
       .根结点的儿子数为, M；
       .除根结点以外的非叶子结点的儿子数为M/2, M；
       .每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
       .非叶子结点的关键字个数指向儿子的指针个数-1；
       .非叶子结点的关键字：K, K, …, KM-1；且Ki  Ki+1；
       .非叶子结点的指针：P, P, …, PM；其中P指向关键字小于K的
子树，PM指向关键字大于KM-1的子树，其它Pi指向关键字属于Ki-1, Ki的子树；
       .所有叶子结点位于同一层；
       如：（M）

B+树
       B+树是B-树的变体，也是一种多路搜索树：
       .其定义基本与B-树同，除了：
       .非叶子结点的子树指针与关键字个数相同；
       .非叶子结点的子树指针Pi，指向关键字值属于Ki, Ki+1的子树
（B-树是开区间）；
       .为所有叶子结点增加一个链指针；
       .所有关键字都在叶子结点出现；

 至于实现，给出一个连接可以看看 https://github.com/begeekmyfriend/bplustree 

然后数据库的键是字符串型的，如果转换出数字呢？答案是用hash算法，网上也有很多经典的实现

这里给出Bizzard公司的经典算法（采用了部分，不是全部）

  cryptTable
	  seed   index1   index2   i
	 index1   index1   index1
		 index2  index1 i   i   i index2  
			  temp1 temp2
			seed  seed      
			temp1  seed    
			seed  seed      
			temp2  seed  
			cryptTableindex2  temp1  temp2
   stdstring key   dwHashType
	  ckey    key
	  seed1   seed2  
	 ch
	 ckey  
		ch  ckey
		seed1  cryptTabledwHashType    ch  seed1  seed2
		seed2  ch  seed1  seed2  seed2    
	 seed1

 暴雪的源码中是用了三次hash值来决定一个数据的，数据冲突的几率是

1: 18889465931478580854784

几乎不可能出现

而我们这里由于纯粹的学习原理而已，所以采用一次就行了

接下来就是要把这两个算法整合进数据库中，用来代替以前的搜索算法

需要对算法进行一定的修改

在下一张章中实现