B、B-、B+、B*-Tree

Ted posted @ 2008年8月21日 21:11 in 未分类 with tags data structure tree , 1742 阅读

B树

即二叉搜索树：

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如：

B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

如：

但B树在经过多次插入与删除后，有可能导致不同的结构：

右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；

实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的策略；

B-树

是一种多路搜索树（并不是二叉的）：

1.定义任意非叶子结点最多只有M个儿子；且M>2；

2.根结点的儿子数为[2, M]；

3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5.非叶子结点的关键字个数=指向儿子的指针个数-1；

6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

8.所有叶子结点位于同一层；

如：（M=3）

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B-树的特性：

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.其搜索性能等价于在关键字全集内做一次二分查找；

5.自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；

由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

B+树

B+树是B-树的变体，也是一种多路搜索树：

1.其定义基本与B-树同，除了：

2.非叶子结点的子树指针与关键字个数相同；

3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

5.为所有叶子结点增加一个链指针；

6.所有关键字都在叶子结点出现；

如：（M=3）

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；

B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

各类Tree总结：

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

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

[回复]

farhan 说:
2020年12月04日 13:31

Hi to everybody, here everyone is sharing such knowledge, so it’s fastidious to see this site, and I used to visit this blog daily métodos de tratamento contra vícios de droga e álcool

[回复]

LEGEND SEO 说:
2020年12月19日 21:05

It was a very good post indeed. I thoroughly enjoyed reading it in my lunch time. Will surely come and visit this blog more often. Thanks for sharing. soap 2 day

[回复]

farhan 说:
2020年12月22日 04:38

Thank you for helping people get the information they need. Great stuff as usual. Keep up the great work!!! лего дупло

[回复]

john sasda 111 说:
2021年1月15日 12:44

Rounding up the guys to devour some barbecued red meat followed by a drunken jaunt to the local "nudie bar" just doesn't seem to be cutting it for today's soon-to-be grooms as they celebrate the end of bachelorhood. After all, it's the Bachelor Party and not the wedding that will be most remembered and talked about event amongst a guy's inner circle. The bachelor party is the ultimate 'boys night out" and now future grooms are stretching this "night out' into a whole weekend affair. bachelor party in Austin

[回复]

전설 서구 说:
2021年1月31日 13:50

Pretty good post. I have just stumbled upon your blog and enjoyed reading your blog posts very much. I am looking for new posts to get more precious info. Big thanks for the useful info. buy Pinterest PVA

[回复]

전설 서구 说:
2021年2月14日 17:24

This is just the information I am finding everywhere. Thanks for your blog, I just subscribe your blog. This is a nice blog.. günstiger schlüsseldienst hannover

[回复]

UMAIR 说:
2021年3月08日 16:19

Surely this site called www.signnow.com is going to remain on top of my list. Due to the fact that this site have almost everything I was looking for. Highly recommended to you guys for right reason.

[回复]

metew36558 说:
2021年3月12日 11:40

Montecrypto casino review: crypto currency heaven?

[回复]

Diniz Z. 说:
2021年6月22日 01:54

cad visit site
c a d visit site
blackberry desktop visit site
best free video editing visit site
apple visit site update
video editing visit site free
systems visit site
scs visit site
nch visit site
visit site companies
visit site ag
ultimate visit site
visit site architect
visit site a g
bmc visit site
graphic design visit site
screen capture visit site
kuta visit site infinite algebra 1
home design visit site
screen recording visit site
vpn visit site
mind mapping visit site
free editing visit site
id visit site
best photo editing visit site
gopro visit site
torrent visit site
free visit site downloads
logitech webcam visit site
mobile visit site
database visit site
visit site developer salary
kuta visit site infinite algebra 2
free cad visit site
payroll visit site
visit site definition
visit site as a service
r visit site
v p n visit site
free animation visit site
logo design visit site
scanner visit site
nokia recovery visit site
dvd burning visit site
arduino visit site
samsung visit site
update visit site
samsung visit site update
new visit site
android visit site
dj mixing visit site
types of visit site
free accounting visit site
dental visit site
agile visit site development
visit site development life cycle phases
sage visit site
windows visit site development kit
tax visit site
spss visit site
hp visit site
shorten visit site

[回复]

Royal CBD 说:
2021年7月15日 18:24

Regular visits listed here are the easiest method to appreciate your energy, which is why why I am going to the website everyday, searching for new, interesting info. Many, thank you Royal CBD

[回复]

n95 说:
2021年7月19日 16:57

Thanks with regard to publishing this type of excellent post! I discovered your site ideal for my personal requirements. It has fantastic as well as useful articles. Continue the great function! n95

[回复]

korea-onlinecasino 说:
2021年7月20日 21:15

Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info.<a href="https://korea-onlinecasino.com">korea-onlinecasino.com</a>

[回复]

Unarmed Guards Los A 说:
2021年7月26日 22:14

Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! It’s always nice when you can not only be informed, but also entertained!

[回复]

California weed disp 说:
2021年8月01日 03:54 Winner of Best of Yolo County 2020 and Best of Weedmaps Kind Farma is Davis California& Premier medical and recreational Cannabis dispensary. California weed dispensary menu

[回复]

asdzxc 说:
2021年8月09日 01:00

Enamel Badges provides a massive range of custom enamel badges in the UK. we offer soft and hard enamel badges, die struck badges, and printed badges. enamel badges

[回复]

no excuses runner 说:
2021年9月06日 17:36

Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post. gas water heater installers near me

[回复]

Faddy 说:
2021年9月09日 16:33

Positive site, where did u come up with the information on this posting? I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. https:// www.allfoodmenuprices.org/

[回复]

Faddy 说:
2021年9月16日 16:17

All your hard work is much appreciated. Nobody can stop to admire you. Lots of appreciation. social media management and marketing

[回复]

Faddy 说:
2021年9月16日 18:43

What a sensational blog! This blog is too much amazing in all aspects. Especially, it looks awesome and the content available on it is utmost qualitative. www.storeholidayhours.org

[回复]

Faddy 说:
2021年9月18日 15:31

I have read your article, it is very informative and helpful for me.I admire the valuable information you offer in your articles. Thanks for posting it.. myloweslifes.org

[回复]

Wolf Cook 说:
2022年2月20日 21:59

Hey, what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you.https://thewolfcook.com/

[回复]

ceva car carrying tr 说:
2022年2月21日 17:01

There are numerous dissertation websites on-line because you additionally obtain obviously stated inside your web site.https://pslogistics.com.au/

[回复]

SEO 说:
2022年4月06日 19:38

This printing center really is one of its kind. Their printouts were really outstanding considering the time given and the price that I paid. It was really worth it thanks to this blog that I read. Here’s the link to their site to https://www.digitekprinting.com/canvas-prints-2 more about their services.

[回复]

school district info 说:
2022年6月14日 19:20

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free

[回复]

online chat 说:
2022年7月30日 02:34

Thank you for helping people get the information they need. Great stuff as usual. Keep up the great work!!!

[回复]

dark web/deep web/d 说:
2022年8月04日 18:52

There is nothing to stop someone from creating thousands of fake links and advertising them on the Internet. dark web links

[回复]

dark web/deep web/d 说:
2022年8月04日 19:36

Some sites also contain embedded images and video, which users often do not want to open and view. In addition, many of these dark web links contain a "pay-per-click" advertising program that allows advertisers to display their ads right in front of millions of web users. deep web

[回复]

dark web/deep web/d 说:
2022年8月04日 19:51

By being cautious about where you post your information and making sure that sites that you visit do not contain harmful embedded scripts, you can reduce your risk of becoming a victim. dark web links

[回复]

dark web/deep web/d 说:
2022年8月04日 20:13

There are many commonalities in these links as well. Some of them are link farms, automated websites, spam links, and phishing scams. There are a few other things as well. dark web sites

[回复]

dark web/deep web/d 说:
2022年8月04日 20:29

You also need to be aware of the fact that when you are looking at these links, you are going to get a lot of information on the site. Some of it might be worth reading, and some could be harmful. So just be careful who you associate with and don't give out credit card numbers online! But you can enjoy the dark web if you learn how to work around the dangers. dark web

[回复]

dark web/deep web/d 说:
2022年8月04日 20:44

Affiliate marketing is all about finding the right product to market, and you have to focus on the right niche in order to make any money at all. work from home jobs

[回复]

dark web/deep web/d 说:
2022年8月04日 21:02

The series went so well that it earned the company $4 million in sales in its first three months. The secret to their affiliate marketing success stories? affiliate marketing success

[回复]

sex chat 说:
2022年8月31日 01:59