B+树是B树的变体,常用于数据库和操作系统的文件系统中。MySQL数据库的索引就是基于B+树实现的。
常见面试题:MySQL数据库的索引实现原理?为什么MySQL数据库的索引是基于B+树实现而不是B树?
本章节不写B+树的代码实现,主要分析MySQL数据库的索引为什么使用B+树实现。
B+树是B树的变体,常用于数据库和操作系统的文件系统中。MySQL数据库的索引就是基于B+树实现的。
常见面试题:MySQL数据库的索引实现原理?为什么MySQL数据库的索引是基于B+树实现而不是B树?
本章节不写B+树的代码实现,主要分析MySQL数据库的索引为什么使用B+树实现。
一个有序链表搜索、添加、删除的平均时间复杂度是多少?$O(n)$
能否利用二分搜索优化有序链表,将搜索、添加、删除的平均时间复杂度降低至 $O(logn)$?
由于链表没有像数组那样的高效随机访问(时间复杂度:$O(1)$),所以不能像有序数组那样直接进行二分搜索优化。
那有没有其他办法让有序链表搜索、添加、删除的平均时间复杂度降低至 $O(logn)$?使用跳表。
如果要经常判断1个元素是否存在,你会怎么做?
很容易想到使用哈希表(HashSet、HashMap),将元素作为key去查找,时间复杂度是$O(1)$,但是空间利用率不高,需要占用比较多的内存资源。
如果需要编写一个网络爬虫去爬10亿个网站数据,为了避免爬到重复的网站,如何判断某个网站是否爬过?很显然,HashSet、HashMap并不是非常好的选择。是否存在时间复杂度低、占用内存较少的方案?布隆过滤器。
提示:动态规划的概念很难把它描述清楚,所以在看目录一的时候,只需要一眼就过,不需要深入理解。接着往下看目录二的案例,大量的案例会让你理解它的使用套路。当你对几个案例有一定理解后,再回头看目录一的概念性内容就会豁然开朗,然后带着你对概念的理解继续看案例,相信你会兴奋的跳起来。