笔记，B+树

B+树面对的场景，是一个有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+树是应用于硬盘的数据结构，常为数据库和文件系统服务。通过增加树的分叉数，降低树的高度，从而减少存储器的访问次数，有提速效果。