你好，我是王健伟。 前面我们在讲串的基本操作的时候，你一定发现了，我们没有提到在一个字符串中寻找子串的问题。这个寻找操作，不仅是这种数据结构中所要面对的最常见的算法，更是最重要的算法之一。这节课，我们就专门来看一看，怎么去找到这个子串。 问题的提出对...

你好，我是王健伟。 上节课我带你学习了串的朴素模式匹配算法，这种算法思想简单，执行效率不高。为什么这么说呢？我带你仔细分析一下。 朴素模式匹配算法的问题串的朴素模式匹配算法经常可以看到主串的指针point1回退的情形。导致匹配时间增加。看一下图1： ...

你好，我是王健伟。 上节课我们针对串的KMP模式匹配算法配以了大量的图形进行了非常仔细的观察，而观察的目的，就是为了这节课代码的实现。 串的KMP模式匹配算法实现代码并不多，但只有你学好了上节课的内容，对该算法有详细的理解，才能理解本节这样写代码的含...

你好，我是王健伟。 上节课介绍的KMP模式匹配算法是通过next数组参与计算来达到加速匹配的目的。但是，在next数组中，因为没考虑当前字符的位置情况，只考虑了字符不匹配时单纯的指针移动问题（point1和point2值的改变），这很可能导致移动后将...

你好，我是王健伟。 字符串方面知识的讲解告一段落后，这次，我们讲一讲跳表相关的知识，也讲一讲大家所关心的一个问题——为什么Redis用跳表实现而MySQL用B+树实现。 在跳表中查询及复杂度分析回顾以往学习过的数组（线性表的顺序存储）和链表（线性表的...

你好，我是王健伟。 这节课我们来看一个新的数据结构——哈希表。 哈希表也叫散列表或Hash表，是由数组演化来的一种扩展，用于存放数据。哈希表跟数组一样，支持查询、插入、删除等操作，但哈希表的表现尤其突出，因为它大大降低了查找数据所消耗的时间。 它是怎...

你好，我是王健伟。 上节课我们在讲解哈希函数的设计方法中提到了“哈希冲突”这个词。 通常来说，在传递给哈希函数不同的参数但返回的哈希值是相同的整数时，就产生了哈希冲突。 这节课，我们就谈一谈如何解决哈希冲突。 如何解决哈希冲突？哈希冲突无法完全避免，...

你好，我是王健伟。 这节课我们来谈一谈多路查找树。传统的、用来搜索的二叉查找树有很多，比如平衡二叉树、红黑树等。 虽然通常情况下它们的查询性能很不错，但当数据量非常大的时候，它们却无能为力。因为当数据量非常大时，内存是很有限的，不可能把所有数据全部加...

你好，我是王健伟。 上节课我们详细讲解了多路查找树中的B树，这节课我们来聊一聊B+树。B+树有人理解为B树的升级，有人理解为B树的变形（变体），都可以。性质上来看，B+树与B树基本相同，但还是有一些不同点的。 B+树的所有非叶子节点中的数据都会包含...

你好，我是王健伟。 B树和B+树在数据库中的应用问题是面试中常考的问题。这节课，我就带你详细分析一下这些数据结构的特点，看看怎么更好地将他们应用在数据库中。 B+树在数据库中的应用举例众所周知，数据库中的数据是保存在硬盘上的。一般来说，一块硬盘由很多...