这是B-Tree合集的第二篇。这部分会实现基本的数据结构和Search。基本数据结构根据Part1介绍的B-Tree的属性，我们可以建立节点型和树型两种基本数据结构BTreeNodestruct{keys[]int//一个键数组tint//最小度数c[]*BTreeNode//子指针数组nint//当前键的个数leafbool//当节点为叶时为真。否则为false}typeBTreestruct{root*BTreeNode//指向根节点的指针tint//最小度}//BTreeNodefuncNewBTreeNode(tint,leafbool)*BTreeNode{return&BTreeNode{keys:make([]int,t<<1-1),t:t,c:make([]*BTreeNode,t<<1),leaf:leaf,}}//构造函数（将树初始化为空）funcNewBTree(tint)*BTree{return&BTree{t:t,}}Search例如要在下面的B树中查找120，那么就从Part1开始可以看出，我们会从根开始，所以下面分三步来查找120。您可以使用以下伪代码来描述Search方法。对于红框，表示找到第一个大于等于k的key索引，但是伪代码代码使用的是顺序查找的方式，是O(N)。从Part1可以看出，节点中的元素是从小到大排列的，所以我们可以采用二分的方式进行优化。//找到第一个大于或等于kfuncfindGE(s[]int,left,right,kint)int{ifleft<=right{mid:=left+(right-left)>>1ifk==s[mid]{returnmid}elseifk>s[mid]{returnfindGE(s,mid+1,right,k)}else{returnfindGE(s,left,mid-1,k)}}returnleft}下面是Search的代码func(n*BTreeNode)search(kint)*BTreeNode{i:=findGE(n.keys,0,n.n-1,k)ifn.keys[i]==k{returnn}ifn.leaf{returnnil}returnn.c[i].search(k)}func(t*BTree)Search(kint)*BTreeNode{ift.root!=nil{returnt.root.search(k)}returnnil}在下一次的Part3中，将实现B-Tree的Insert。
