【Data Structure】平衡多路查找树（Balanced Multi-way Search Tree） - B+ 树（B+ Tree）

B+ 树（B+ Tree）

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-04-04

【Data Structure】平衡多路查找树（Balanced Multi-way Search Tree） - B树（B-Tree）

B树（B-tree）

在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以 $O (l o g_{2} n)$ 的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的平衡查找树，因为其一个节点可以拥有多于2个子节点，因而也可以称为 多路自平衡查找树（Multi-way Self-balancing Search Tree），简称为多路查找树。

...

Posted by Wei on 2019-06-04, Last Modified on 2025-04-04

【Data Structure】平衡多路查找树（Balanced Multi-way Search Tree）- 2-3 查找树和 2-4 查找树

背景

**二叉查找树（Binary Search Tree）**在很多情况下可以良好的工作，但它的限制是最坏情况下的时间复杂度为 O(n)。

**平衡二叉查找树（Self-balancing Binary Search Tree）**的设计则是保证其高度在最坏的情况下时间复杂度为 $O (l o g_{2} n)$ ，其插入、删除和查找操作的时间复杂度均为 $O (l o g_{2} n)$ 。常见的平衡二叉查找树包括 AVL树、红黑树。

**多路平衡查找树（Multi-way Self-balancing Search Tree）**作为一般化的平衡二叉查找树（Self-balancing Binary Search Tree），现在其实存在很多种类的平衡查找树，常见的有2-3查找树、2-4查找树、B 树、B+树等。

...

Posted by Wei on 2019-06-04, Last Modified on 2025-04-04

【Algorithm】查找算法（Search）

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。

顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想

顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值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-04-04

【Network】Charles 为什么可以获取 HTTPS 包内容

背景

之前，我们在【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-04-23

西维蜀黍