不说别的见源码
#coding=utf-8
import sys, os
import bisect
import string
class Entity(object):
"""data entity"""
__slots__ = ("key", "value",)
def __init__(self, key, value):
self.key = key
self.value = value
def __str__(self):
return self.key
def __unicode__(self):
return self.__str__()
def __cmp__(self, key):
if key > self.key:
return 1
elif key == self.key:
return 0
else:
return -1
class Node(object):
"""B Node"""
#__slots__ = ("parent", "entities", "childes",)
def __init__(self):
self.parent = None
self.entities = []
self.childes = []
def find(self, key):
i = bisect.bisect_left(self.entities, key)
if i != len(self.entities) and self.entities[i].key == key:
return self.entities[i].value
def delete(self, key):
"""delete key"""
i = bisect.bisect_left(self.entities, key)
if i != len(self.entities) and self.entities[i].key == key:
e = self.entities[i]
del self.entities[i]
return i, e
else:
return None, None
def is_leaf(self):
return len(self.childes) == 0
def add_entity(self, entity):
self.entities.append(entity)
self.entities.sort(key=lambda x:x.key)
def add_child(self, node):
self.childes.append(node)
node.parent = self
self.childes.sort(key=lambda x:x.entities[0].key)
class BTree(object):
def __init__(self, size=6):
self.size = size
self.root = None
self.length = 0
def add(self, key, value=None):
self.length += 1
if self.root:
current = self.root
while not current.is_leaf():
for i, e in enumerate(current.entities):
if e.key > key:
current = current.childes[i]
break
elif e.key == key:
e.value = value
return
else:
current = current.childes[-1]
current.add_entity(Entity(key, value))
if len(current.entities) > self.size:
self._split_(current)
else:
#init root
self.root = Node()
self.root.add_entity(Entity(key, value))
def _split_(self, node):
"""Rules
1、middle index node become parent
2、create right Nodes move parents right go to this node
"""
middle = len(node.entities) / 2
top = node.entities[middle]
right = Node()
for e in node.entities[middle + 1:]:
right.add_entity(e)
for n in node.childes[middle + 1:]:
right.add_child(n)
left = node
left.entities = node.entities[:middle]
left.childes = node.childes[:middle + 1]
parent = node.parent
if parent:
parent.add_child(right)
parent.add_entity(top)
if len(parent.entities) > self.size:
self._split_(parent)
else:
self.root = Node()
self.root.add_entity(top)
self.root.add_child(left)
self.root.add_child(right)
def get(self, key):
e, v = self._find_node_(key)
return v
def _find_node_(self, key):
if self.root:
current = self.root
while current.entities:
bisect.bisect_left(current.entities, key)
for i, e in enumerate(current.entities):
if e.key > key:
current = current.childes[i]
break
elif e.key == key:
return e, e.value
else:
current = current.childes[-1]
def delete(self, key):
"""#一般都标记删除不真删除"""
pass
def bfs(root):
"""Iterator traverses a tree in breadth-first order."""
queue = []
queue.append(root)
while len(queue) > 0:
node = queue.pop(0)
yield node
for child in node.childes:
queue.append(child)
return
if __name__ == '__main__':
t = BTree()
for i in xrange(26):
key = string.lowercase[i % 26]
value = i
t.add(key, value)
root = t.root
print "generate tree ......"
for node in bfs(root):
if node.parent:
print "parent",
for e in node.parent.entities:
print e,
print
for e in node.entities:
print e,
print
print
print "test btree get"
for i in xrange(26):
key = string.lowercase[i % 26]
print key, t.get(key), "-",
分享到:
相关推荐
数据结构BTree B-Tree B+Tree B*Tree 的特征说明
sqlite-btree sqlite-btree sqlite-btree
BTree,B-Tree,B+Tree,BTree都是什么.doc
BtreeNET是基于磁盘的.NET Btree库,理论上它支持8.589.934.592 GB的文件大小! 您可以修改源代码以在PHP或任何其他COM支持的编程语言中使用该库。
2.BTree.h,BTree.cpp:B树的声明、实现代码 3.BPlusTree.h,BPlusTree.cpp:B+树的声明、实现代码,注:大多数的函数,B和B+都是一样的,但是我还是分开写了,比如输出函数 4.Context.h:策略方法的实现 5.mian.cpp:...
BTree-Real-Estate-:使用Django Framework构建的完全成熟的房地产Web应用程序
Btree源代码 C中有关高并发B树源代码的工作项目。您可能希望下载单独的数据库项目以获取最新版本。 大多数C文件都可以在Windows和Linux下编译。 多根节点子目录中正在研究的一个想法通过创建最新更新的根版本的只读...
#二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $right = null; } #@param $btree 二叉树根节点 function breadth_first_traverse($btree) { $...
Oracle-Btree索引,索引的ppt
演示BTree的操作
B树的数据结构,由C语言实现,做数据库先要学习的数据结构
btree 索引btree 索引btree 索引
图书馆管理系统,3阶b树 数据结构实验,简单易懂 初学者的作品
BTree B+Tree B*Tree的一点入门总结
二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。...
java版本的高效,稳定Btree源代码
在Common Lisp中实现的B树。 将键/值对存储到基于磁盘的数据结构中。 当前的实现已通过SBCL进行了测试。 该项目最初位于Alien-consader.org,但现在可以在SourceForge上使用。
google开源的btree的源码,希望多看看这个源码。
用c++实现,用的demo演示btree怎么实现 vc下实现
类似于 STL std::map 、 std::set 、 std::multimap和std::multiset模板,这个库提供了btree::map 、 btree::set 、 btree::multimap和btree::multiset 。 这与 Google 的原始项目不同,因为容器的行为更像现代 ...