面试系列-数据引擎实现的数据结构

1. ⼆叉查找树，图一

插⼊数据是有序的，如[5,10,15,20,30,25,35]，那么结构就变成图二这样

⼆叉树的优缺点：

1. 查询数据的效率不稳定，若树左右⽐较平衡的时，最差情况为O(logN)，如果插⼊数据是有序的，退化为了链表，查询时间变成了O(N)
2. 每次查找数据就需要从磁盘中读取一个节点，一个节点对应一个磁盘块。数据量⼤的情况下，会导致树的⾼度变⾼，如果每个节点对应磁盘的⼀个块来存储⼀条数据，需io次数⼤幅增加，显然⽤此结构来存储数据是不可取的
3. B-树

可以看出使⽤B-树定位某个值还是很快的(10亿数据中3次io操作+内存中⼆分法)，但是也是有缺点的：B-不利于范围查找，⽐如上图中我们需要查找[15,36]区间的数据，需要访问7个磁盘块（1/2/7/3/8/4/9），io次数又上去了，范围查找也是我们经常⽤到的，所以b-树也不太适合在磁盘中存储需要检索的数据。

1. b+树

b+树与b-树的⼏点不同：

1. b+树中⼀个节点如果有k个关键字，最多可以包含k个⼦节点（k个关键字对应k个指 针）；⽽b-树对应k+1个⼦节点（多了⼀个指向⼦节点的指针）

2. b+树除叶⼦节点之外其他节点值存储关键字和指向⼦节点的指针，⽽b-树还存储了数据，这样同样⼤⼩情况下，b+树可以存储更多的关键字

3. b+树叶⼦节点中存储了所有关键字及data，并且多个节点⽤链表连接，从上图中看⼦节点中数据从左向右是有序的，这样快速可以⽀撑范围查找（先定位范围的最⼤值和 最⼩值，然后⼦节点中依靠链表遍历范围数据）

B-Tree和B+Tree该如何选择？

1. B-Tree因为⾮叶⼦结点也保存具体数据，所以在查找某个关键字的时候找到即可返回。⽽B+Tree所有的数据都在叶⼦结点，每次查找都得到叶⼦结点。所以在同样⾼度的B-Tree和B+Tree中，B-Tree查找某个关键字的效率更⾼。
2. 由于B+Tree所有的数据都在叶⼦结点，并且结点之间有指针连接，在找⼤于某个关键字或者⼩于某个关键字的数据的时候，B+Tree只需要找到该关键字然后沿着链表遍历就可以了，⽽B-Tree还需要遍历该关键字结点的根结点去搜索。
3. 由于B-Tree的每个结点（这⾥的结点可以理解为⼀个数据页）都存储主键+实际数据，⽽B+Tree⾮叶⼦结点只存储关键字信息，⽽每个页的⼤⼩有限是有限的，所以同⼀页能存储的B-Tree的数据会⽐B+Tree存储的更少。这样同样总量的数据，B-Tree的深度会更⼤，增⼤查询时的磁盘I/O次数，进⽽影响查询效率。