前几天我写了点btree的东西(http://thuhak.blog.51cto.com/2891595/1261783)，今天继续这个思路，继续写b+tree。而且b+tree才是我的目的，更加深入理解文件和数
前几天我写了点btree的东西()，今天继续这个思路，继续写b+tree。
而且b+tree才是我的目的，更加深入理解文件和数据库索引的基本原理。
腾讯云AI代码助手
基于混元代码大模型的AI辅助编码工具
98 查看详情 
立即学习“Python免费学习笔记（深入）”；
在之前，我一直只把b+tree当成是btree的一种变形，或者说是在某种情况下的一种优化，另外一些情况可能还是btree好些。但是做完之后才发现，b+tree在各种情况都可以完全取代btree，香港虚拟主机，并能够让索引性能得到比btree更好的优化。因为b+tree设计的核心要点，是为了弥补btree最大的缺陷。
立即学习“Python免费学习笔记（深入）”；
btree最大的缺陷是什么?
首先,我们知道对于btree和b+tree这种多路搜索树来说，一个很重要的特点就是树的度数非常大。因为只有这样才能够降低树的深度，减少磁盘读取的次数。而树的度数越大，叶子节点在树中的比例就越大。假设度数为1000，那么叶子节点比他上一层内部节点的数量至少要多1000倍，在上一层就更加可以忽略不计了。可以说树种99.9%的节点都是叶子节点。 但是对于btree来说，所有节点都是一样的结构，都含有一定数量的数据和指向节点的指针。这两项数据占据btree节点的几乎全部的空间。一个节点内的数据的数量比硬盘指针的数量少一，可以说和指针的数量几乎相等。对于python这种动态类型语言感觉不出来，但是对于C这种固定类型语言来说，即使这个children list数组为空，这个数组的空间也都是预留出去的。导致的结果就是占绝大多数的叶子节点的children list指针数组所占的磁盘空间完全浪费。
一个数据的大小和硬盘指针的大小取决于key-value中key和value大小的比值。假如说这个比值是2:1。那么btree浪费了几乎1/3的空间。
b+tree针对这个问题的，把叶子节点和内节点的数据结构分开设计，让叶子节点不存放指针。因此同样大小的叶子节点，b+tree所能包含数据数量要比btree大。按照上面的假设就是大1/2。数的深度很可能比btree矮，大范围搜索或遍历所需要的载入磁盘的次数也少。
立即学习“Python免费学习笔记（深入）”；
另外，b+tree还有一个特点是所有数据都存放在叶子节点，这些叶子节点也可以组成一个链表，并把这个链表的表头拿出来，方便直访问数据。有些文章认为这对于范围搜索来说是个巨大的优化。但是就我的看法，这个特性最大的作用仅仅是让代码更容易一些，性能上，只会比树的遍历差，而不会比树的遍历好。因为不管是用指向叶子节点的指针搜，还是用树的遍历搜，所搜索的节点的数量都是几乎相同的。在相同大小的范围搜索的性能，只取决于访问顺序的连续性。从树根向下遍历，那么一次可以取得大量的子节点的范围，并针对这些节点做访问排序，得到更好的访问连续性。如果是沿着指向兄弟节点的指针搜索，一是兄弟节点也许是后插入的，存放并不一定和自己是连续的，二是只有每次从硬盘中将改节点载入到内存，才知道兄弟节点放在硬盘哪个位置，这又变成了对硬盘的一个随机的同步操作，性能的下降可想而知。
说b+tree因为有指向兄弟节点的指针方便数据库扫库这种结论，是不正确的。
立即学习“Python免费学习笔记（深入）”；
还是上代码吧,依旧只是在内存对数据结构插入删除查找的模拟
#!/usr/bin/env pythonfrom random import randint,choicefrom bisect import bisect_right,bisect_leftfrom collections import dequeclass InitError(Exception):passclass ParaError(Exception):passclass KeyValue(object):__slots__=(‘key’,’value’)def __init__(self,key,value):self.key=keyself.value=valuedef __str__(self):return str((self.key,self.value))def __cmp__(self,key):if self.key>key:return 1elif self.key==key:return 0else:return -1class Bptree_InterNode(object):def __init__(self,M):if not isinstance(M,int):raise InitError,’M must be int’if M=self.M-1def isempty(self):return len(self.ilist)self.Ldef isempty(self):return len(self.vlist)M:raise InitError,’L must be less or equal then M’else:self.__M=Mself.__L=Lself.__root=Bptree_Leaf(L)self.__leaf=self.__root@propertydef M(self):return self.__M@propertydef L(self):return self.__Ldef insert(self,key_value):node=self.__rootdef split_node(n1):mid=self.M/2newnode=Bptree_InterNode(self.M)newnode.ilist=n1.ilist[mid:]newnode.clist=n1.clist[mid:]newnode.par=n1.parfor c in newnode.clist:c.par=newnodeif n1.par is None:newroot=Bptree_InterNode(self.M)newroot.ilist=[n1.ilist[mid-1]]newroot.clist=[n1,newnode]n1.par=newnode.par=newrootself.__root=newrootelse:i=n1.par.clist.index(n1)n1.par.ilist.insert(i,n1.ilist[mid-1])n1.par.clist.insert(i+1,newnode)n1.ilist=n1.ilist[:mid-1]n1.clist=n1.clist[:mid]return n1.pardef split_leaf(n2):mid=(self.L+1)/2newleaf=Bptree_Leaf(self.L)newleaf.vlist=n2.vlist[mid:]if n2.par==None:newroot=Bptree_InterNode(self.M)newroot.ilist=[n2.vlist[mid].key]newroot.clist=[n2,newleaf]n2.par=newleaf.par=newrootself.__root=newrootelse:i=n2.par.clist.index(n2)n2.par.ilist.insert(i,n2.vlist[mid].key)n2.par.clist.insert(i+1,newleaf)newleaf.par=n2.parn2.vlist=n2.vlist[:mid]n2.bro=newleafdef insert_node(n):if not n.isleaf():if n.isfull():insert_node(split_node(n))else:p=bisect_right(n.ilist,key_value)insert_node(n.clist[p])else:p=bisect_right(n.vlist,key_value)n.vlist.insert(p,key_value)if n.isfull():split_leaf(n)else:returninsert_node(node)def search(self,mi=None,ma=None):result=[]node=self.__rootleaf=self.__leafif mi is None and ma is None:raise ParaError,’you need setup searching range’elif mi is not None and ma is not None and mi>ma:raise ParaError,’upper bound must be greater or equal than lower bound’def search_key(n,k):if n.isleaf():p=bisect_left(n.vlist,k)return (p,n)else:p=bisect_right(n.ilist,k)return search_key(n.clist[p],k)if mi is None:while True:for kv in leaf.vlist:if kv
立即学习“Python免费学习笔记（深入）”；
实现过程和btree很像，不过有几点显著不同。
1.内节点不存储key-value，只存放key
2.沿着内节点搜索的时候，香港服务器租用，查到索引相等的数要向树的右边走。所以二分查找要选择bisect_right
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/522088.html
微信扫一扫 
支付宝扫一扫 
