6
6
2014
54

B树

1.B数B-树。(B数即B-树)

B数的数据可能很庞大,不能将所有数据都读入内存,故内存缓存B树的一部分数据。我们要尽量保证每次读入尽可能多的信息。正由于这个原因,一个结点的大小通常相当于一个完整的磁盘页。因此,一个B树结点可以拥有的子女数就由磁盘页的大小决定。

也可以说B树的设计目的:减少磁盘的读、写操作

 

(1)B数每个叶子节点具有相同的深度

(2)每个结点能包含的关键字数有一个上界和下界。这些节用B数的最小度数的固定整数t>=2来表示

  (2.1)非根结点必须至少有t-1个关键字,即每个非根结点至少有t个子女。

  (2.2)如果树非空,则根节点至少包含一个关键字。

  (2.3)每个结点可以包含至多2t-1个关键字。故一个节点内至多有2t个子女,若一个结点是满的,则它有2t-1个关键字

(3)每个结点x有以下域:

   (3.1)n[x]该结点的关键字书

   (3.2)n[x]个关键字。这n[x]个关键字以非降序排列。key1[x]<=key2[x]...

   (3.3)leaf[x],x为叶子,则为true.若为内部结点,则为false

4.每个内结点包含n[x]+1个指向子女的指针。c1[x],c2[x],...

5.关键字keyi[x]对存储在各个子树中的关键字加以分隔:若ki为存储在ci[x]为根子树的关键字中,则

k1<=key1[x]<=k2<=key2[x]......

 

B树中并非只有叶子节点才存数据,中间节点也存数据

 

2.B+树

B+数和B数的差异:

1.有n颗子树的结点中含有n个关键字。

2.所有的叶子节点中包含了全部关键字的信息,即指向含有这些关键字记录的指针。

3.所有的非终端结点看成索引部分,结点中仅含有其子树根节点的最大(或者最小)关键字。而B数非终端结点页包含了的有效信息。

why??B+数比B树更适合文件索引和数据库索引。

首先B+ B树对比二叉树:B+ B具有多个分支,相比二叉树来说深度降低,一个结点对应着一次io操作,所以深度降低,则查找一个元素降低了访盘的次数!

然后比较B+ 与 B树,由于B+树的非叶子节点只存储索引信息,而B树还存储需要查找的有信息,所以B+树一个结点的索引信息更多。如果把所有同一内部结点的关键字放在同一盘中,那么关键字数量就越多。相对IO次数就降低了。

而且,只有非终结点并没有指向文件内容,所以死任何关键字的查找都要走一条从根到叶子节点的路径,长度相同,所以效率相当。

 

3 B*-Tree

B*树是在B+树上的改进:

B+树分裂:当一个结点满时,则分配一个新的结点,将原来结点1/2的数据复制到新节点,最后在父节点中增加新节点的指针。故B+树的分裂影响原结点和父节点。

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

所以说B*树是一颗丰满的树。B*树保证了非叶子节点的块利用率 >= 2/3 。所以相对B+树空间利用率更高

 

 

推荐参考:

http://www.360doc.com/content/11/1103/13/6938655_161335261.shtml

Category: 算法、数据结构 | Tags: | Read Count: 2395
Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月08日 00:35 Great article Lot's of information to Read...Great Man Keep Posting and update to People..Thanks 123movies websites
Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月14日 23:16

I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You. Wedding Videographer New Jersey

Avatar_small
jackjohnny 说:
2021年8月15日 19:38

Great post, and great website. Thanks for the information! solarmovie

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月17日 13:55

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks... 안전놀이터

Avatar_small
jackjohnny 说:
2021年8月17日 22:55

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with extra information? It is extremely helpful for me. 123movies.wiki

Avatar_small
jackjohnny 说:
2021年8月18日 20:03

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. soap2day.com

Avatar_small
jackjohnny 说:
2021年8月19日 20:21

i never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. https://soap2day.sbs/ [url=https://soap2day.sbs/]https://soap2day.sbs/[/url]

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月20日 17:53

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! Aesthetic.co.uk

Avatar_small
jackjohnny 说:
2021年8月23日 16: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. thong tac cong hoang mai

Avatar_small
seoservise 说:
2021年8月23日 17:01

You delivered such an impressive piece to read, giving every subject enlightenment for us to gain information. Thanks for sharing such information with us due to which my several concepts have been cleared. lawyer for murder defense in Dallas

Avatar_small
jackjohnny 说:
2021年8月23日 21:36

This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!. smm panel template

Avatar_small
seoservise 说:
2021年8月24日 15:46

Superior post, keep up with this exceptional work. It's nice to know that this topic is being also covered on this web site so cheers for taking the time to discuss this! Thanks again and again! Dentitox Pro Reviews

Avatar_small
Pune Call Girls 说:
2021年8月25日 18:06

Thanks so much for sharing this awesome info! I am looking forward to see more postsby you!

Avatar_small
jackjohnny 说:
2021年8月28日 20:14

Thanks for the blog post buddy! Keep them coming... satta

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月29日 23:31

I found this is an informative and interesting post so i think so it is very useful and knowledgeable. I would like to thank you for the efforts you have made in writing this article. binary options signals software

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月30日 03:14

You delivered such an impressive piece to read, giving every subject enlightenment for us to gain information. Thanks for sharing such information with us due to which my several concepts have been cleared. Search Engine List

Avatar_small
jackjohnny 说:
2021年8月30日 19:07

Hello There. I found your blog using msn. This is an extremely well written article. I will be sure to bookmark it and return to read more of your useful information. Thanks for the post. I’ll certainly comeback. matka chart

Avatar_small
jackjohnny 说:
2021年8月31日 23:09

I admire what you have done here. I like the part where you say you are doing this to give back but I would assume by all the comments that this is working for you as well. matka

Avatar_small
jackjohnny 说:
2021年9月04日 16:19

Thank you very much for writing such an interesting article on this topic. This has really made me think and I hope to read more. kalyan satta

Avatar_small
jackjohnny 说:
2021年9月05日 20:23

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. voyance par tel

Avatar_small
jackjohnny 说:
2021年9月06日 21:06

Thanks for a very interesting blog. What else may I get that kind of info written in such a perfect approach? I’ve a undertaking that I am simply now operating on, and I have been at the look out for such info. artificial leather

Avatar_small
balance-sheet 说:
2021年9月06日 22:03

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers.

Avatar_small
link 说:
2021年9月07日 21:24

If you are looking for more information about flat rate locksmith Las Vegas check that right away. <a href="https://ibiza55.com/article/%e0%b9%84%e0%b8%ae%e0%b9%82%e0%b8%a5%e0%b8%ad%e0%b8%ad%e0%b8%99%e0%b9%84%e0%b8%a5%e0%b8%99%e0%b9%8c/">แอพคาสิโน</a>

Avatar_small
jackjohnny 说:
2021年9月08日 16:53

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. Coffee

Avatar_small
seoservise 说:
2021年9月08日 21:41 hello!! Very interesting discussion glad that I came across such informative post. Keep up the good work friend. Glad to be part of your net community. 250 dofollow blog comments
Avatar_small
jackjohnny 说:
2021年9月11日 21:30

I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work... 바둑이게임

Avatar_small
matka satta 说:
2021年9月12日 14:41

Great post, please keep on sharing amazing article like this! It makes me happy reading your post

Avatar_small
link 说:
2021年9月12日 19:06

I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work... เสือมังกร ออนไลน์

Avatar_small
matka result 说:
2021年9月13日 18:07

Thank you so much for sharing this great blog.Very inspiring and helpful too.Hope you continue to share more of your ideas.I will definitely love to read.

Avatar_small
seoservise 说:
2021年9月14日 03:28 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. here
Avatar_small
jackjohnny 说:
2021年9月14日 19:56

I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work... เสือมังกร ออนไลน์

Avatar_small
golden matka 说:
2021年9月15日 16:30

it's miles a gratifying internet site.. The design seems thoroughly to your liking.. hold enthusiastic later that!.

Avatar_small
tellaldi 说:
2021年9月18日 23:55

International Market place for Smar*****ches, GPS, Fitness, Waterproof, Fitness Smart wach,

Avatar_small
Digital Ali 说:
2021年9月21日 01:42

Please continue this great work and I look forward to more of your awesome blog posts. buy youtube comments

Avatar_small
satta matka 说:
2021年9月26日 18:20

Great knowledge, do anyone mind merely reference back to it

Avatar_small
sattamatka 说:
2021年9月28日 18:53

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers.

Avatar_small
satta 说:
2021年9月30日 15:07

I realize this is one of the most meaningful counsel for me. And i am vivacious studying your article. however have to commentary upon some standard matters, the internet site style is unmodified; the articles are invincible. thank you for the ton of actual and viable explicit.

Avatar_small
matka 说:
2021年10月02日 19:02

cool stuff you have got and you keep update all of us.

Avatar_small
Greatpeople me 说:
2021年10月02日 23:31

Wow, What an exceptional pronounce. i found this too much informatics. it's miles what i used to be searching for for. i'd as soon as to area you that absorb keep sharing such kind of data.If realistic, thank you.

Avatar_small
krogerexperiencee 说:
2021年10月02日 23:46

I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work

Avatar_small
jackjohnny 说:
2021年10月04日 21:04

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. voyance sérieuse téléphone sans attendre

Avatar_small
Digital Ali 说:
2021年10月08日 15:16

Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome! cheap transcription services

Avatar_small
Digital Ali 说:
2021年10月09日 19:07

Thank you so much for the post you do. I like your post and all you share with us is up to date and quite informative, i would like to bookmark the page so i can come here again to read you, as you have done a wonderful job. คาสิโนออนไลน์ฟรีเงิน

Avatar_small
seoservise 说:
2021年10月10日 16:41

Thanks for every other informative site. The place else may just I get that kind of information written in such an ideal means? I have a venture that I’m just now operating on, and I have been on the look out for such information. 먹튀폴리스

Avatar_small
Digital Ali 说:
2021年10月11日 12:38

I found that site very usefull and this survey is very cirious, I ' ve never seen a blog that demand a survey for this actions, very curious... ej high school musical

Avatar_small
link 说:
2021年10月12日 18:55

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers. North American Bancard Agent Program

Avatar_small
pandaexpress 说:
2021年10月18日 15:02

I am very much pleased with the contents you have mentioned. I wanted to thank you for this great article.

Avatar_small
seoservise 说:
2021年10月26日 02:50

I learn some new stuff from it too, thanks for sharing your information. voyance telephone

Avatar_small
Digital Ali 说:
2021年10月27日 13:45

Outstanding article! I want people to know just how good this information is in your article. Your views are much like my own concerning this subject. I will visit daily your blog because I know. It may be very beneficial for me. cheap gaming laptop under 300

Avatar_small
Digital Ali 说:
2021年11月06日 03:50 I was reading your article and wondered if you had considered creating an ebook on this subject. Your writing would sell it fast. You have a lot of writing talent. pkv games apk download
Avatar_small
visum fur indien 说:
2021年11月13日 19:29

I was surfing net and fortunately came across this site and found very interesting stuff here. Its really fun to read. I enjoyed a lot. Thanks for sharing this wonderful information.

Avatar_small
wedding ceremony vid 说:
2021年11月20日 17:50

This is my first visit to your web journal! We are a group of volunteers and new activities in the same specialty. Website gave us helpful data to work.

Avatar_small
Επείγουσα Βίζα Καναδ 说:
2021年11月28日 22:48

Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts.

Avatar_small
johny 说:
2022年7月13日 20:02

I prefer merely excellent resources - you will see these people in: Low End Shaders Minecraft 1.19


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com