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
2021年8月08日 00:35 Great article Lot's of information to Read...Great Man Keep Posting and update to People..Thanks 123movies websites
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
2021年8月15日 19:38
Great post, and great website. Thanks for the information! solarmovie
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... 안전놀이터
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
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
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]
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
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
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
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
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
2021年8月25日 18:06
Thanks so much for sharing this awesome info! I am looking forward to see more postsby you!
2021年8月28日 20:14
Thanks for the blog post buddy! Keep them coming... satta
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
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
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
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
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
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
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
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.
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>
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
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
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... 바둑이게임
2021年9月12日 14:41
Great post, please keep on sharing amazing article like this! It makes me happy reading your post
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... เสือมังกร ออนไลน์
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.
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
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... เสือมังกร ออนไลน์
2021年9月15日 16:30
it's miles a gratifying internet site.. The design seems thoroughly to your liking.. hold enthusiastic later that!.
2021年9月18日 23:55
International Market place for Smar*****ches, GPS, Fitness, Waterproof, Fitness Smart wach,
2021年9月21日 01:42
Please continue this great work and I look forward to more of your awesome blog posts. buy youtube comments
2021年9月26日 18:20
Great knowledge, do anyone mind merely reference back to it
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.
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.
2021年10月02日 19:02
cool stuff you have got and you keep update all of us.
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.
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
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
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
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. คาสิโนออนไลน์ฟรีเงิน
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. 먹튀폴리스
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
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
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.
2021年10月26日 02:50
I learn some new stuff from it too, thanks for sharing your information. voyance telephone
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
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
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.
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.
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.
2022年7月13日 20:02
I prefer merely excellent resources - you will see these people in: Low End Shaders Minecraft 1.19
2022年8月31日 03:15
Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place.. formation gestion d'entreprise
2022年9月03日 22:04
NBSE Model Paper 2023 Blueprint Available Students you can Download in Pdf format form this web page below given links. HSSLC Regular and Private Students Prepare their Exam from these Sample Papers, Students have to Register for Appearing in Public Exam 2023. Nagaland Board Model Paper Nagaland Board HSSLC Model Paper 2023 has announced State Governmental Board of Education, Nagaland Board Students who are going to sit in Public Examination 2023 are allowed to Download Nagaland Board HSSLC Sample Paper 2023 Download our web Portal.
2022年10月19日 15:23
Please let me know if you’re looking for a article author for your weblog. You have some really good posts and I believe I would be a good asset. If you ever want to take some of the load off, I’d love to write some articles for your blog in exchange for a link back to mine. Please send me an email if interested. You can check out my work here: <ahref="https://minecraftwild.com/baritone-autominer/">Baritone AutoMiner</a>
2022年10月29日 23:45
It is my first visit to your blog, and I am very impressed with the articles that you serve. Give adequate knowledge for me. Thank you for sharing useful material. I will be back for the more great post. gramhir
2022年10月31日 16:20
Marriage is a holy union that should be respected and sealed with official documentation. In Haryana State, marriage registration is a compulsory task for all married couples. These works under the marriage registration Act 2008. Haryana Marriage Certificate Registration 2023 The marriage certificate is a legal document that proves that a person is legally married to the other. The certificates also help in name changing, acquiring a passport and VISA. The state government calls for an online marriage registration certificate.
2022年11月23日 00:52 Thanks for the nice blog. It was very useful for me. I'm happy I found this blog. Thank you for sharing with us,I too always learn something new from your post. Satta king
2022年11月27日 17:38
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. deep web
2023年2月04日 14:08
Internet is something we all use every second of our lives now with WiFi gadgets, where you can test the speed at any time, and where notifications, texts, and emails stream down like rain, we should always have the best Internet connection with us. WiFi Speed Test We've talked a lot about the importance of having a decent Internet connection, but now it's time for you to take action and see whether your Internet is what it claims to be. We will use SpeedTest by Ooakla to check your WiFi speed, which is equivalent to your Internet connection speed.
2023年9月05日 17:56
I appreciate everything you have added to my knowledge base.Admiring the time and effort you put into your blog and detailed information you offer.Thanks. EuroTogel Login