关于索引中如何运行二分法查询的问题

Question

老师好！想请教一个mysql b+树索引的问题。都说mysql的索引数据页，查询时是通过二分法找到要查数据所在的下一页指针。但是比如我做索引的字段是一个varchar的索引数据页或者主键索引叶子节点中的数据，长度可变，那如何在从文件中读出页的16k数据中做二分法呢？还是说读出整个页到内存，再遍历一遍在内存中序列化，再做二分法呢？

Answer 1

sqlercn 2020-03-22 14:43:50

Innodb从磁盘读取数据的最小单位就是页，也就是说一次会把整个页都读到内存中。

• 提问者 烈焰卡卡 #1

  恩呢，我可能有点较真了。。。我理解的二分法，是直接读出数据页的数据就可以二分了。但由于数据长度不同，读到内存中如果还需要从头到尾把这一页遍历一遍在内存中给序列化一下，再二分法查找，不就是相当于读出来之后直接像链表一样从头直接找就行了，二分法不是有点多此一举？

• sqlercn 回复 提问者 烈焰卡卡 #2

  数据读到内存中时都是按定义的字段的大小分配置内存的，比如varchar(100)不论是你存了100个字符还是只存了一个字符都会分配100个字符的内存空间。单纯的把数据加载到内存和实际的找到需要的数据在处理效率上还是不相同的，所以二分法还是有效的。

• 提问者 烈焰卡卡 回复 sqlercn #3

  老师我晕了。。。varchar不是变长么，100也只是字符，可能是100字节也可能300字节，我记得varchar是有单独空间保存字符实际长度。所以varchar这种变长字段的存在才会导致数据长度也是不确定的。按照定义字段大小分配空间是怎么讲

点开查看后面2条评论