黑马程序员技术交流社区

标题: 【上海校区】: 二叉树数据结构与B_tree数据结构的对比 [打印本页]

---

作者: lsl.tutu    时间: 2018-4-26 18:12
标题: 【上海校区】: 二叉树数据结构与B_tree数据结构的对比


与一个结点两个分支的二叉树(又叫二元树)相比，B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的           目的。B-树的查找很简单，是二叉排序树的扩展，二叉排序树是二路查找，B-树是多路查找，可以减少访问硬盘次数为目的，是一种平衡多路查找树.


B-Tree就是我们常说的B树，一定不要读成B减树，否则就很丢人了。B树这种数据结构常常用于实现数据库索引，因为它的查找效率比较高。
这里的B并不是binary的意思，而是balance（平衡树又称平衡多路查找树）的意思。


图示比较:
1.二叉树数据结构

2. B-tree数据结构  

在mysql数据库中，用到的数据结构是——B-Tree B-tree平均比较次数logN

logN就是采用了分治发进行形式 (二分法，三分法，四分法) 具体的2，3，4对于整个复杂度的影响是很小的，只是差了一个常数系，所以都归为一类

m阶的B-tree特点:
树种每个节点最多m个孩子，
除根节点和叶子节点外，至少两个孩子。
如果根节点不是叶子节点，则至少两个孩子。
所有叶子节点都出现在同一层，叶子节点不包含任何关键字信息
每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
a) Ki (i=1…n)为关键字，且关键字按顺序排序K(i-1)< Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： ceil(m / 2)-1 <= n <= m-1。

相关扩展:

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于

走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键

字范围的子结点；

所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点

中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率

从1/2提高到2/3；

---

作者: 吴琼老师    时间: 2018-7-5 16:50

---

作者: 不二晨    时间: 2018-7-10 14:53
奈斯

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2