树与存储
一个根节点,每个节点下挂着最多2个子节点。、
概念:
度:结点的分支数,二叉树度为2。
深度:树的层次。
二叉排序树:
二叉树的基础上,每个节点上都有一个数字,节点上的数字都比右节点上的大。
应用场景:
基于内存的排序数据结构,写入时将数据写入到对应的位置。数据可能会出现倾斜,可以想到数字写入顺序如果不是50-20-60-18-55,而是18-20-50-55-60,那么二叉树就会退变为链表。
B-树:
B-树每个节点上包含着数据和指针,每个指针指向其一个子节点的位置,并且数据的个数为指针的2d-1个。这里的d是指针的个数,同时也是树的“度”。
B-树的查找需要一次对每个节点进行二分查找,直至找到或返回null。通常,可以引入布朗过滤器等方式加速查找。
B-树的写入、删除时要进行分裂、合并、转移等操作,越是非顺序的插入就越容易碰到这些高性能消耗的操作。
应用场景:
一般B-树常常作为磁盘的查找的数据结构使用。
一般磁盘为了减少寻道时间,往往会进行预读,一次读入1个或多个page的数据。我们只要将B-树的每个节点控制在一个page大小,就可以保证,磁盘一次的查找只需要一次IO。一个page大小一般在4k,可以存储不少的数据,假设一个节点存储数据量为100,深度为3的B-树,即可保存100w数据量(100*100*100),而100的数据一般用不了4k的存储空间。
当然,这里节点中存储的东西主要包括data和指针,指针大小是固定的,而数据有大有小。只要控制好每个数据块的大小,就可以提高B-树的性能。
另外,一般情况下非叶子节点占用空间一般较小,上面的例子中,非叶子节点数据量只有1w,完全可以缓存至内存中,这点也是在实际数据库实现中常常使用到的优化。
B+树:
B+树完全是对B-树的工程级优化,非叶子节点不在存储data,只有根节点才存储数据。最大程度的加大了单个page中指针的个数,增加数的度。减少了树的层次。
另外相比较于B-树,其key的个数变为指针个数的2d个。
应用场景:
实际在数据库系统中使用时,往往每个叶子节点都会存储一个其相邻节点的一个指针,用来在范围查找时有更好的性能。
建议继续学习:
- HFile存储格式 (阅读:14411)
- 淘宝图片存储架构 (阅读:9646)
- 我对技术方向的一些反思 (阅读:9684)
- 海量小文件存储 (阅读:7381)
- HBase技术介绍 (阅读:6577)
- 存储基础知识之——硬盘接口简述 (阅读:5919)
- 在perl中连接和使用sqlite做数据存储 (阅读:4917)
- 如果用户在5分钟内重复上线,就给他发警告,问如何设计? (阅读:4812)
- Redis新的存储模式diskstore (阅读:4348)
- HTML5本地存储初探(二) (阅读:4330)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:shiming 来源: 淘宝网综合业务平台团队博客
- 标签: 存储 树
- 发布时间:2012-08-03 00:18:12
- [684] Go Reflect 性能
- [26] 正态分布的前世今生(一)
- [17] rsync同步的艺术
- [16] Linux Used内存到底哪里去了?
- [14] 基于HTTP缓存轻松实现客户端应用的离线支持
- [14] Linux内存中的Cache真的能被回收么?
- [13] 关于RDS只读实例延迟分析
- [13] 我的git笔记
- [13] Cuckoo Filter:设计与实现
- [12] 在JavaScript中什么时候使用==是正