网站建设 设计创意,网站粘度计算公式,wordpress导入有道笔记,有没有公司直招的网站B树面对的场景#xff0c;是一个有10亿行的表#xff0c;希望某一列是有序的。这么大的数据量#xff0c;内存里放不下#xff0c;需要放在硬盘里。结果#xff0c;原本运行于内存的二叉树#xff0c;就升级为B树了。
在二叉树中#xff0c;每个节点存储着一个数字树面对的场景是一个有10亿行的表希望某一列是有序的。这么大的数据量内存里放不下需要放在硬盘里。结果原本运行于内存的二叉树就升级为B树了。
在二叉树中每个节点存储着一个数字通过比大小产生两个分叉所以叫二叉树。在B树中比如说每个节点储存999个数字它能产生1000个分叉对应地有1000个硬盘指针储存在节点中。
B树的第一层是一个根节点放在内存里。其中999个数字连续存储通过二分查找法快速地找出目标数字位于哪个区间它对应一个硬盘指针。然后从硬盘上读取对应的那个第二层中的节点进入内存。继续查找找到第三层、第四层节点。例如第四层节点是叶子结点则它的指针指向最终的数据。
B树仅在叶子结点存储数据在非叶子结点存储索引。
“最终的数据”可以是记录的地址。一个表中的10亿条记录按照添加时的顺序存储需要按照某一列保持有序时以B树做索引10亿个有序的硬盘指针指向10亿个乱序的记录。有可能表有多列并有多个B树索引为这一个表服务。
一个四层的1000叉树有1000的三次方个叶子节点即10亿条记录。多数情况下这足够多了。通过3次硬盘操作就能在10亿条记录中找到一个这是二叉树做不到的。计算以2为底的10亿的对数得29.90要进行约30次硬盘操作才能找到。所以二叉树是内存里的数据结构而B树是为硬盘设计的。
另外叶子节点构成双链表方便进行范围查询即查询某列大于a小于b的所有记录。如果不是因为有范围查询的要求用哈希表更快。
以上是B树的一般形态一个有10亿行的表的某列需要做有序索引。一般来说那一列是个数字可如果是字符串呢且长度不确定B树的节点中要储存999个字符串吗如果一个数字有8字节而一个字符串平均100字节节点中可能存不下999个字符串或是存下了但节点变长。
B树的一般形态节点长度是确定的如16KB。如果节点长度可变那会是种什么情形另外向B树添加、删除数据时会引起树的不平衡需要专门的应对策略。
如果把硬盘指针换成网络指针B树能否成为分布式数据库的索引呢一个网络指针的设计方案2字节计算机编号6字节硬盘地址。它可以管理65536台计算机每台计算机有256TB存储。
总结B树是应用于硬盘的数据结构常为数据库和文件系统服务。通过增加树的分叉数降低树的高度从而减少存储器的访问次数有提速效果。
