面试系列-mysql数据结构

1. ⼆叉查找树，图一

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

⼆叉树的优缺点：

1. 查询数据的效率不稳定，若树左右⽐较平衡的时，最差情况为O(logN)，如果插⼊数 据是有序的，退化为了链表，查询时间变成了O(N)
2. 数据量⼤的情况下，会导致树的⾼度变⾼，如果每个节点对应磁盘的⼀个块来存储⼀

条数据，需io次数⼤幅增加，显然⽤此结构来存储数据是不可取的

1. 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次数，进⽽影响查询效率。