B+树（B+ Tree）是B树的一种变体，B+树也属于平衡多路查找树（Multi-way Search Tree）。
大体结构与B树相同，包含根节点、内部节点和叶子节点。与B树唯一的区别在于，B+树的内部节点不保存数据元素的value，只保存key（而B树的内部节点既保存数据元素的key，也保存数据元素的value），因此B+树能在内存中存放更多索引，增加缓存命中率。另外因为叶子节点相连遍历操作很方便，而且数据也具有顺序性，便于区间查找。
Posted by Wei on 2019-06-05, Last Modified on 2025-08-11
在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以$O(log_2n)$的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的平衡查找树，因为其一个节点可以拥有多于2个子节点，因而也可以称为多路自平衡查找树（Multi-way Self-balancing Search Tree），简称为多路查找树。
Posted by Wei on 2019-06-04, Last Modified on 2025-08-11
**二叉查找树（Binary Search Tree）**在很多情况下可以良好的工作，但它的限制是最坏情况下的时间复杂度为 O(n)。
**平衡二叉查找树（Self-balancing Binary Search Tree）**的设计则是保证其高度在最坏的情况下时间复杂度为 $O(log_2n)$，其插入、删除和查找操作的时间复杂度均为 $O(log_2n)$。常见的平衡二叉查找树包括 AVL树、红黑树。
**多路平衡查找树（Multi-way Self-balancing Search Tree）**作为一般化的平衡二叉查找树（Self-balancing Binary Search Tree），现在其实存在很多种类的平衡查找树，常见的有2-3查找树、2-4查找树、B 树、B+树等。
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。
顺序查找适合于存储结构为顺序存储或链接存储的线性表。
顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n);
所以，顺序查找的时间复杂度为O(n)。
Posted by Wei on 2019-06-03, Last Modified on 2025-08-11
之前，我们在【Security】HTTPS 和 【Security】安全的 HTTP 的演化中介绍了HTTPS的工作原理，HTTPS的一个重要的作用，就是防止中间人攻击（Man-in-the-Middle Attack，MITM）。
然而，不知道你有没有考虑过，作为一个常用的macOS下抓包工具 - Charles，它是如何获取到HTTPS包中明文内容的。
Posted by Wei on 2019-05-31, Last Modified on 2025-08-11
哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数（Hash function），存放元素的数组称做散列表（Hash table）。
Posted by Wei on 2019-05-30, Last Modified on 2025-08-11
在了解赫夫曼树之前，我们首先先介绍一些基础概念。
路径是指在一棵树中，从一个节点到另一个节点之间的分支构成的通路。
Posted by Wei on 2019-05-30, Last Modified on 2023-02-21
在 1972 年，慕尼黑理工大学（Technical University of Munich）的计算机科学家 Rudolf Bayer 创造了**红黑树（Red-Black Tree）**数据结构。
除了包含数据和左右孩子节点之外，红黑树的节点还包含了一项特别的信息 – 颜色。这个颜色只包含两种颜色，即红色和黑色。
在 1962 年，俄罗斯数学家 G. M. Andel’son-Vel-skii 和 E. M. Landis 发明了第一种自平衡二叉查找树，叫做 AVL 树。AVL 树必须维持如下平衡条件，对每个节点 n：节点 n 的左子树的高度与右子树的高度的差至多是 1。
🐒 Software engineer | 📷 Photographer | 👹 Urban explorer
