Skip to content

MySQL 索引知识点

17-6月-18
  1. 存储引擎负责 MySQL 中数据的存储和提取。

  2. 索引是存储引擎用于快速找到记录的一种数据结构。

  3. 索引可以包含一个或多个列的值。如果索引包含多个列,那么列的顺序也十分重要,因为 MySQL 只能高效地使用索引的最左前缀列。

  4. 有时候需要索引很长的字符列,这会让索引变得大且慢。对于 BLOBTEXT 或者很长的 VARCHAR 类型的列,必须使用前缀索引,因为 MySQL 不允许索引这些列的完整长度。

    mysql> ALTER TABLE sakila.city_demo ADD INDEX (city(7));
    
  5. 索引合并策略 type: index_merge 有时候是一种优化的结果,但实际上更多时候说明了表上的索引建得很糟糕:

    • 当出现服务器对多个索引做相交操作时 Extra: Using intersect(film_id,actor_id)(通常有多个 AND 条件),通常意味着需要一个包含所有相关列的多列索引,而不是多个独立的单列索引。

    • 当服务器需要对多个索引做联合操作时 Extra: Using union(film_id,actor_id)(通常有多个 OR 条件),通常需要耗费大量 CPU 和内存资源在算法的缓存、排序和合并操作上。

  6. 如果一个索引包含所有需要查询的字段的值,我们就称之为 覆盖索引 Extra: Using index

  7. MySQL 可以使用同一个索引既满足排序,又用于查找行。因此,如果可能,设计索引时应该尽可能地同时满足这两种任务。如果 EXPLAIN 出来的 type: index,则说明 MySQL 使用了索引扫描来做排序。

    • 只有当索引的列顺序和 ORDER BY 子句的顺序完全一致,并且所有列的排序方向都一样时,MySQL 才能够使用索引来对结果做排序。

    • ORDER BY 子句和查找型查询的限制是一样的:需要满足索引的最左前缀的要求;否则,MySQL 都需要执行排序操作,而无法利用索引排序。有一种情况下 ORDER BY 子句可以不满足索引的最左前缀的要求,就是前导列为常量的时候。

      # 例如,KEY rental_date(rental_date,inventory_id,customer_id)
      
      # 可以使用 rental_date 索引做排序的查询示例:
      ... WHERE rental_date = '2005-05-25' ORDER BY inventory_id, customer_id;
      ... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC;
      ... WHERE rental_date > '2005-05-25' ORDER BY rental_date, inventory_id; // ORDER BY 使用的两列就是索引的最左前缀
      
      # 不可以使用 rental_date 索引做排序的查询示例:
      ... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC, customer_id ASC; // 使用了两种不同的排序方向
      ... WHERE rental_date = '2005-05-25' ORDER BY inventory_id, staff_id; // 引用了一个不在索引中的列
      ... WHERE rental_date = '2005-05-25' ORDER BY customer_id; // 无法组合成索引的最左前缀
      ... WHERE rental_date > '2005-05-25' ORDER BY inventory_id, customer_id; // 索引列的第一列上是范围条件,所以 MySQL 无法使用索引的其余列       
      
  8. 理想情况下扫描的行数和返回的行数应该是相同的。

  9. EXPLAIN 语句中的 type 列反应了访问类型。访问类型有很多种,从全表扫描到索引扫描、范围扫描、唯一索引查询、常数引用等。

  10. 查询优化、索引优化、库表结构优化需要齐头并进,一个不落。

MySQL 查询执行过程

03-6月-18

当希望 MySQL 能够以更高的性能运行查询时,最好的办法就是弄清楚 MySQL 是如何优化和执行查询的。

当向 MySQL 发送一个请求的时候,MySQL 到底做了些什么:

  1. 客户端发送一条查询给服务器。

  2. 服务器先检查查询缓存,如果命中了缓存,则立刻返回存储在缓存中的结果。否则进入下一阶段。

  3. 服务器端进行 SQL 解析、预处理,再由优化器生成对应的执行计划。

    • 首先,MySQL 通过关键字将 SQL 语句进行解析,并生成一颗对应的“解析树”。MySQL 解析器将使用 MySQL 语法规则验证和解析查询。例如,它将验证是否使用错误的关键字,或者使用关键字的顺序是否正确等,再或者它还会验证引号是否能前后正确匹配。
    • 预处理器则根据一些 MySQL 规则进一步检查解析树是否合法,例如,这里将检查数据表和数据列是否存在,还会解析名字和别名,看看它们是否有歧义。下一步预处理器会验证权限。
    • 现在语法树被认为是合法的了,并且由优化器将其转化成执行计划。一条查询可以有很多种执行计划,最后都返回相同的结果。优化器的作用就是找到这其中最好的执行计划。
  4. MySQL 根据优化器生成的执行计划,调用存储引擎的 API 来执行查询。

  5. 将结果返回给客户端。如果查询可以被缓存,那么 MySQL 在这个阶段也会将结果存放到查询缓存中。

扩展:

1. 分解关联查询的好处?

  • 对 MySQL 的查询缓存来说,如果关联中的某个表发生了变化,那么就无法使用查询缓存了,而拆分后,如果某个表很少改变,那么基于该表的查询就可以重复利用查询缓存结果了。
  • 将查询分解后,执行单个查询可以减少锁的竞争。

2. 优化 LIMIT 分页。

  • 在偏移量非常大的时候(翻页到非常靠后的页面),例如可能是 LIMIT 10000,20 这样的查询,这时 MySQL 需要查询 10020 条记录然后只返回最后 20 条,前面 10000 条记录都将被抛弃。
  • LIMIT 和 OFFSET 的问题,其实是 OFFSET 的问题,它会导致 MySQL 扫描大量不需要的行然后再抛弃掉。如果可以记录上次取数据的位置,那么下次就可以直接从该书签记录的位置开始扫描,这样就可以避免使用 OFFSET。

    mysql> SELECT * FROM sakila.rental ORDER BY rental_id DESC LIMIT 20;
    
    // 假设上面的查询返回的是主键为 16049 到 16030 的记录,那么下一页查询就可以从 16030 这个点开始:        
    mysql> SELECT * FROM sakila.rental WHERE rental_id < 16030 ORDER BY rental_id DESC LIMIT 20;
    
    * 该技术的好处是无论翻页到多么后面,其性能都会很好。 
    

PHP 内核中的变量

28-5月-18

PHP 变量在内核中的存储方式

在 Zend 引擎中是怎么可以做到一个变量保存任何的数据类型呢?打开 Zend/zend.h 头文件,会发现以下一些结构体:

typedef struct _zval_struct zval;

typedef union _zvalue_value {
    long lval;              // long, bool, resource
    double dval;            // double
    struct {                // string(len 保存字符串长度,val 保存字符串的值)
        char *val;   
        int len;
    } str;

    HashTable *ht;          // array
    zend_object_value obj;  // object            
} zvalue_value;

struct _zval_struct {
    zvalue_value value;     // 变量的值
    zend_uint refcount;     // 变量引用数
    zend_uchar type;        // 变量的类型
    zend_uchar is_ref;      // 变量是否被引用
};

zval 结构体就是通常用到的 PHP 变量在内核中的表示方式。在 zval 结构体中,可以看到 4 个成员变量。

zval 结构体的 value 成员变量是一个 zvalue_value 联合体,从 zvalue_value 联合体的成员变量中可以看出,不同的类型会保存到不同的成员变量中,这样就实现了 PHP 变量可以存储任何数据类型。

引用计数器与写时复制

zval 结构中有以下两个成员变量用于引用计数器:

  • is_ref: BOOL 值,标识变量是否是引用集合。
  • refcount: 计算指向引用集合的变量个数。

一个 zval 结构的实体称为 zval 容器。在 PHP 语言层创建一个变量就会相应地在 PHP 内核中创建一个 zval 容器。

<?php
$a = "this is variable";
xdebug_debug_zval('a');
// 输出 --> a: (refcount=1, is_ref=0),string 'this is variable' (length=16)

$b = $a;    // 此时 $a 和 $b 指向同一内存块
xdebug_debug_zval('a');
// 输出 --> a: (refcount=2, is_ref=0),string 'this is variable' (length=16)

$a = "changed value";
xdebug_debug_zval('a');
// 输出 --> a: (refcount=1, is_ref=0),string 'changed value' (length=13)

当将变量 $a 的值赋给变量 $b 时,变量 $a 的 refcount 增加 1,所以这时候变量 $a 和变量 $b 是指向同一内存块的。当改变变量 $a 的值时,发现 refcount 的值变回 1,所以这时候变量 $a 和变量 $b 指向不同的内存块,这就是 写时复制机制。就是两个指向同一内存块的变量,当其中一个变量的值发生变化,才会另外创建一个内存块去保存新的值。

<?php
$a = 1;
xdebug_debug_zval('a');
// 输出 --> a: (refcount=1,is_ref=0),int 1

$b = &$a;
xdebug_debug_zval('a');
// 输出 --> a: (refcount=2,is_ref=1),int 1

$b += 5;
xdebug_debug_zval('a');
// 输出 --> a: (refcount=2,is_ref=1),int 6

当显式地让一个变量引用另一个变量时,变量的 is_ref 字段会设置为 1,表示此变量被引用,另外引用计数器(refcount)也相应地加 1。

PHP 新特性

22-5月-18

现代的 PHP 语言有很多令人兴奋的新特性,这些新特性让 PHP 语言变成了一个强大的平台,为构建 Web 应用和命令行工具提供了愉快的体验。

这些特性中有些不是必不可少的,不过能让我们的开发工作更轻松。而有些特性则非常重要,例如命名空间,这是现代 PHP 标准的基础,能让现代的 PHP 开发者顺其自然地使用一些开发实践(例如自动加载)。

1. 性状

性状是 PHP 5.4.0 引入的新概念,是类的部分实现,可以混入一个或多个现有的 PHP 类中。

性状有两个作用:表明类可以做什么(像是接口);提供模块化实现(像是类)。

<?php
// 定义性状
trait MyTrait {
    // 这里是性状的实现
}

// 使用性状
class MyClass
{
    use MyTrait;

    // 这里是类的实现
}

2. 生成器

PHP 生成器(generator)是 PHP 5.5.0 引入的功能。生成器是简单的迭代器,与标准的 PHP 迭代器不同,PHP 生成器不要求类实现 Iterator 接口,从而减轻了类的负担。

<?php
// 一个简单的生成器
function myGenerator() {
    yield 'value1';
    yield 'value2';
    yield 'value3';
}

// 调用并迭代生成器
foreach (myGenerator() as $yieldedValue) {
    echo $yieldedValue, PHP_EOL;
}

上述代码的输出如下:      
    value1
    value2
    value3

3. 闭包

闭包和匿名函数在 PHP 5.3.0 中引入。闭包是指在创建时封装周围状态的函数。匿名函数其实就是没有名称的函数。

注意:理论上讲,闭包和匿名函数是不同的概念。不过,PHP 将其视作相同的概念。

<?php
// 创建闭包
$closure = function($name) {
    return sprintf('Hello %s', $name);
};

echo $closure("Josh");
// 输出 --> "Hello Josh"

// 把状态附加到 PHP 闭包上
function enclosePerson($name) {
    return function($doCommand) use ($name) {
        return sprintf('%s, %s', $name, $doCommand);
    };
}

// 把字符串 "Clay" 封装在闭包中
$clay = enclosePerson('Clay');

// 传入参数,调用闭包
echo $clay('get me sweet tea!');    
// 输出 --> "Clay, get me sweet tea!"

具名函数 enclosePerson() 有个名为 $name 的参数,这个函数返回一个闭包对象,而且这个闭包封装了 $name 参数。

4. 内置的 HTTP 服务器

从 PHP 5.4.0 起,PHP 内置了 Web 服务器。

// 打开终端,进入项目根目录,本地启动一个监听端口为 4000 的 PHP Web 服务器
php -S localhost:4000

// 使用指定的初始化文件
php -S localhost:4000 -c app/config/php.ini

// 查明使用的是否为内置的服务器
if (php_sapi_name() === 'cli-server') {
    // PHP 内置的 Web 服务器
} else {
    // 其他 Web 服务器
}

Linux 常见服务配置

28-4月-18

https 配置

编辑 /etc/sysconfig/iptables 文件,开放 443 端口

-A INPUT -m state --state NEW -m tcp -p tcp --dport 443 -j ACCEPT

修改 nginx 配置文件

server
{
    listen 443;
    server_name www.163100.com;
    ssl on;
    ssl_certificate /alidata/server/ssl/1_www.163100.com_bundle.crt;
    ssl_certificate_key /alidata/server/ssl/2_www.163100.com.key;

    root                /alidata/www/www.163100.com;
    charset             utf-8;
    index               index.html index.htm index.php;

    ssl_session_timeout 5m;
    ssl_protocols SSLv2 SSLv3 TLSv1;
    #ssl_ciphers ALL:!ADH:!EXPORT56:RC4+RSA:+HIGH:+MEDIUM:+LOW:+SSLv2:+EXP;
    ssl_ciphers HIGH:!aNULL:!MD5:!EXPORT56:!EXP;
    ssl_prefer_server_ciphers   on;


    location ~ .*\.(php)?$
    {
        fastcgi_pass  127.0.0.1:9000;
        fastcgi_index   index.php;
        include fastcgi.conf;
        fastcgi_param HTTPS on;
    }

    #access_log  /alidata/log/nginx/access/www.163100.com.log;
    access_log  off;
    error_log  /alidata/log/nginx/error/www.163100.com.log notice;
    include /alidata/server/nginx/conf/rewrite/default.conf;
}

http 自动跳转到 https

server 
{
    listen       80;
    server_name  www.163100.com;
    rewrite ^(.*)$  https://$host$1 permanent;
}

不带 www 的域名跳转到带 www 上(301 重定向)

server_name  www.163100.com 163100.com;
if ($host != 'www.163100.com')
{
    rewrite ^/(.*)$ http://www.163100.com/$1 permanent;
}

MySQL 事务隔离级别

23-4月-18

mysql 拥有分层的架构。上层是服务器层的服务和查询执行引擎,下层则是存储引擎。

mysql 支持 LOCK TABLESUNLOCK TABLES 语句,这是在服务器层实现的,和存储引擎无关。

mysql 服务器层 不管理事务,事务(行级锁)是由下层的存储引擎实现的。

事务

事务就是一组原子性的 SQL 查询,或者说一个独立的工作单元。事务内的语句,要么全部执行成功,要么全部执行失败。

银行应用是解释事务必要性的一个经典例子。假设一个银行的数据库有两张表:支票(checking)表和储蓄(savings)表。现在要从某个用户的支票账户转移 200 美元到他的储蓄账户,事务 SQL 的样本如下:

1 START TRANSACTION;
2 SELECT balance FROM checking WHERE customer_id = 10233276;
3 UPDATE checking SET balance = balance - 200.00 WHERE customer_id = 10233276;
4 UPDATE savings  SET balance = balance + 200.00 WHERE customer_id = 10233276;
5 COMMIT;

1. 事务的标准 ACID 特性

  1. 原子性(atomicity)
    • 一个事务必须被视为一个不可分割的最小工作单元,整个事务中的所有操作要么全部提交成功,要么全部失败回滚,对于一个事务来说,不可能只执行其中的一部分操作,这就是事务的原子性。
  2. 一致性(consistency)
    • 数据库总是从一个一致性的状态转换到另一个一致性的状态。一致性是对数据可见性的约束,保证在一个事务中的多次操作的数据中间状态对其它事务不可见,这些中间状态是一个过渡状态,与事务的开始状态和事务的结束状态是不一致的。在前面的例子中,一致性确保了,即使在执行第三、四条语句之间时系统崩溃,支票账户中也不会损失 200 美元。
  3. 隔离性(isolation)
    • 通常来说,一个事务所做的修改在最终提交以前,对其他事务是不可见的。在前面的例子中,当执行完第三条语句、第四条语句还未开始时,此时有另外一个账户汇总程序开始运行,则其看到的支票账户的余额并没有被减去 200 美元。
  4. 持久性(durability)
    • 一旦事务提交,则其所做的修改就会永久保存到数据库中。

原子性和一致性的侧重点不同:原子性关注状态,要么全部成功,要么全部失败。而一致性关注数据的可见性。

2. 隔离级别

在 SQL 标准中定义了四种隔离级别,每一种级别都规定了一个事务中所做的修改,哪些在事务内和事务间是可见的,哪些是不可见的。较低级别的隔离通常可以执行更高的并发,系统的开销也更低。

下面简单地介绍一下四种隔离级别:

隔离级别 脏读可能性 不可重复读可能性 幻读可能性 加锁读
READ UNCOMMITTED Yes Yes Yes No
READ COMMITTED No Yes Yes No
REPEATABLE READ No No Yes No
SERIALIZABLE No No No Yes
  1. READ UNCOMMITTED(未提交读)
    • 在 READ UNCOMMITTED 级别,事务中的修改,即使没有提交,对其他事务也都是可见的。事务可以读取未提交的数据,这也被称为 脏读(Dirty Read)
  2. READ COMMITTED(提交读)
    • 大多数数据库系统的默认隔离级别都是 READ COMMITTED(但 MySQL 不是)。READ COMMITTED 满足:一个事务开始时,只能“看见”已经提交的事务所做的修改。换句话说,一个事务从开始直到提交之前,所做的任何修改对其他事务都是不可见的。这个级别有时候也叫做 不可重复读(nonrepeatable read),因为两次执行同样的查询,可能会得到不一样的结果。
  3. REPEATABLE READ(可重复读)
    • REPEATABLE READ 解决了脏读的问题。保证了在同一个事务中多次读取同样记录的结果是一致的。但是理论上,可重复读隔离级别无法解决幻读问题。所谓幻读,指的是当某个事务在读取某个范围内的记录时,另外一个事务又在该范围内插入了新的记录,当之前的事务再次读取该范围的记录时,会产生 幻行(Phantom Row)。InnoDB 和 XtraDB 存储引擎通过 多版本并发控制(MVCC) 解决了幻读的问题。
    • 可重复读是 MySQL 的默认事务隔离级别。
  4. SERIALIZABLE(可串行化)
    • SERIALIZABLE 强制事务串行执行,避免了前面说的幻读问题。简单来说,SERIALIZABLE 会在读取的每一行数据上都加锁,所以可能导致大量的超时和锁挣用问题。

3. 死锁

死锁是指两个或者多个事务在同一资源上相互占用,并请求锁定对方占用的资源,从而导致恶性循环的现象。

例如,设想下面两个事务同时处理 StockPrice 表:

事务 1
    START TRANSACTION;
    UPDATE StockPrice SET close = 45.50 WHERE stock_id = 4 and date = '2002-05-01';
    UPDATE StockPrice SET close = 19.80 WHERE stock_id = 3 and date = '2002-05-02';
    COMMIT;     

事务 2
    START TRANSACTION;
    UPDATE StockPrice SET close = 20.12 WHERE stock_id = 3 and date = '2002-05-02';
    UPDATE StockPrice SET close = 47.20 WHERE stock_id = 4 and date = '2002-05-01';
    COMMIT;

如果凑巧,两个事务都执行了第一条 UPDATE 语句,更新了一行数据,同时也锁定了改行数据,接着每个事务都尝试去执行第二条 UPDATE 语句,却发现改行已经被对方锁定,然后两个事务都等待对方释放锁,同时又持有对方需要的锁,则陷入死循环。除非有外部因素介入才可能解除死锁。

MyISAM 表锁不会产生死锁。InnoDB 目前处理死锁的方法是,将持有最少行级排他锁的事务进行回滚(这是相对简单的死锁回滚算法)。

参考资料

数据库事务原子性、一致性是怎样实现的?

PHP 笔试猴子选大王

22-4月-18

猴子选大王是一个典型的编程问题,一般可用链表(可以用很大的数)或者 while 循环(使用此办法不能用太大的数)解决。

问题描述

n 只猴子围坐成一个圈,按顺时针方向从 1 到 n 编号。然后从 1 号猴子开始沿顺时针方向从 1 开始报数,报到 m 的猴子出局,再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个猴子,它就是大王。要求编程模拟此过程,输入 m、n,输出最后那个大王的编号。

解决方法

<?php
/**
 * 猴子选大王
 * @param int $m 数到第 m 只踢出
 * @param int $n 猴子总数
 */
function king($n, $m)
{
    // 生成数组
    $arr = range(1, $n);    
    $i = 1; // 从 1 开始数
    while (count($arr) > 1) {
        if ($i % $m  == 0) {
            unset($arr[$i-1]);
        } else {
            // 本轮非出局的猴子放在数组尾部
            array_push($arr, $arr[$i-1]);
            unset($arr[$i-1]);
        }
        $i++;
    }
    return $arr;
}

扩展资料

  1. PHP 高级研发工程师面试题总结

PHP 四种基础算法

21-4月-18

一. 冒泡排序

冒泡排序步骤如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

实现示例

function bubbleSort($arr)
{
    $len = count($arr);
    // 该层循环控制需要冒泡的轮数
    for ($i=0; $i<$len; $i++) {
        // 该层循环控制每轮冒出一个数需要比较的次数
        for ($j=0; $j<$len-$i-1; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp; 
            }
        }
    }   
    return $arr;
}

二. 快速排序

快速排序步骤如下:

  1. 从数列中挑出一个元素,称为”基准”(pivot)。
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

示例动画

占位图

实现示例

function quickSort($arr)
{
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }

    $k = $arr[0]; // 基准数    
    $leftArr = array();
    $rightArr = array();
    for ($i=1; $i<$len; $i++) {
        if ($arr[$i] <= $k) {       // 比基准数小的元素放在基准左边   
            $leftArr[] = $arr[$i]; 
        } elseif ($arr[$i] > $k) {  // 比基准数大的元素放在基准右边
            $rightArr[] = $arr[$i]; 
        }
    }
    $leftArr = quickSort($leftArr);
    $rightArr = quickSort($rightArr);
    return array_merge($leftArr, array($k), $rightArr);
}

三. 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n 个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

示例动画

占位图

实现示例

function selectSort($arr) 
{
    $len = count($arr);
    for ($i=0; $i<$len-1; $i++) {
        $min = $i;
        for ($j=$i+1; $j<$len; $j++) {
            if ($arr[$min] > $arr[$j]) {
                $min = $j;
            }
        }
        // 如果最小值的位置和当前假设的位置 $i 不同,则位置互换
        if ($min != $i) {
            $temp = $arr[$min];
            $arr[$min] = $arr[$i];
            $arr[$i] = $temp;
        }
    }   
    return $arr;
}

四. 插入排序

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序步骤如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

示例动画

占位图

实现示例

function insertSort($arr)
{
    for ($i=1; $i<count($arr); $i++) {
        if ($arr[$i-1] > $arr[$i]) {
            $temp = $arr[$i];
            for ($j=$i-1; $j>=0 && $arr[$j]>$temp; $j--) {
                $arr[$j+1] = $arr[$j];              
            }
            $arr[$j+1] = $temp;
        }
    }
    return $arr;
}

程序执行过程

15-3月-18

以下是 hello.c 的 C 语言源程序代码。

#include <stdio.h>

int main()
{
    printf("hello, world\n");
}

Unix 系统上,从源文件到目标文件的转化是由编译器驱动程序完成的:

linux> gcc -o hello hello.c

在这里,GCC 编译器驱动程序读取源程序文件 hello.c,并把它翻译成一个可执行目标文件 hello。这个翻译过程可分为四个阶段完成,如图所示。执行这四个阶段的程序(预处理器、编译器、汇编器和链接器)一起构成了编译系统(compilation system)。

类图

  • 预处理阶段。预处理器(cpp)根据以字符 # 开头的命令,修改原始的 C 程序。比如 hello.c 中第 1 行的 #include <stdio.h> 命令告诉预处理器读取系统头文件 stdio.h 的内容,并把它直接插入程序文本中。结果就得到了另一个 C 程序,通常是以 .i 作为文件扩展名。

  • 编译阶段。编译器(ccl)将文本文件 hello.i 翻译成文本文件 hello.s,它包含一个汇编语言程序。对同一台机器来说,不管什么高级语言,编译转换后的输出结果使用的都是同一种机器级代码。

  • 汇编阶段。接下来,汇编器(as)将 hello.s 翻译成机器语言指令,把这些指令打包成一种叫做 可重定位目标程序(relocatable object program) 的格式,并将结果保存在目标文件 hello.o 中。hello.c 文件是一个二进制文件,它包含的 17 个字节是函数 main 的指令编码。

  • 链接阶段。请注意,hello 程序调用了 printf 函数,它是每个 C 编译器都提供的标准 C 库中的一个函数。printf 函数存在一个名为 printf.o 的单独的预编译好了的目标文件中,而这个文件必须以某种方式合并到我们的 hello.o 程序中。链接器(ld)就负责处理这种合并。结果就得到 hello 文件,它是一个可执行目标文件(或者简称为可执行文件),可以被加载到内存中,由系统执行。

TCP 四次握手断开连接(图解)

26-2月-18

建立连接非常重要,它是数据正确传输的前提;断开连接同样重要,它让计算机释放不再使用的资源。如果连接不能正常断开,不仅会造成数据传输错误,还会导致套接字不能关闭,持续占用资源,如果并发量高,服务器压力堪忧。

建立连接需要三次握手,断开连接需要四次握手,可以形象的比喻为下面的对话:

  • [Shake 1] 套接字 A:“任务处理完毕,我希望断开连接。”
  • [Shake 2] 套接字 B:“哦,是吗?请稍等,我准备一下。”
  • 等待片刻后……
  • [Shake 3] 套接字 B:“我准备好了,可以断开连接了。”
  • [Shake 4] 套接字 A:“好的,谢谢合作。”

下图演示了客户端主动断开连接的场景:

TCP 断开连接图解

建立连接后,客户端和服务器都处于 ESTABLISED 状态。这时,客户端发起断开连接的请求:

1)客户端调用 close() 函数后,向服务器发送 FIN 数据包,进入 FIN_WAIT_1 状态。FIN 是 Finish 的缩写,表示完成任务需要断开连接。

2)服务器收到数据包后,检测到设置了 FIN 标志位,知道要断开连接,于是向客户端发送“确认包”,进入 CLOSE_WAIT 状态。

注意:服务器收到请求后并不是立即断开连接,而是先向客户端发送“确认包”,告诉它我知道了,我需要准备一下才能断开连接。

3)客户端收到“确认包”后进入 FIN_WAIT_2 状态,等待服务器准备完毕后再次发送数据包。

4)等待片刻后,服务器准备完毕,可以断开连接,于是再主动向客户端发送 FIN 包,告诉它我准备好了,断开连接吧。然后进入 LAST_ACK 状态。

5)客户端收到服务器的 FIN 包后,再向服务器发送 ACK 包,告诉它你断开连接吧。然后进入 TIME_WAIT 状态。

6)服务器收到客户端的 ACK 包后,就断开连接,关闭套接字,进入 CLOSED 状态。

关于 TIME_WAIT 状态的说明

客户端最后一次发送 ACK 包后进入 TIME_WAIT 状态,而不是直接进入 CLOSED 状态关闭连接,这是为什么呢?

TCP 是面向连接的传输方式,必须保证数据能够正确到达目标机器,不能丢失或出错,而网络是不稳定的,随时可能会毁坏数据,所以机器 A 每次向机器 B 发送数据包后,都要求机器 B ”确认“,回传 ACK 包,告诉机器 A 我收到了,这样机器 A 才能知道数据传送成功了。如果机器 B 没有回传 ACK 包,机器 A 会重新发送,直到机器 B 回传 ACK 包。

客户端最后一次向服务器回传 ACK 包时,有可能会因为网络问题导致服务器收不到,服务器会再次发送 FIN 包,如果这时客户端完全关闭了连接,那么服务器无论如何也收不到 ACK 包了,所以客户端需要等待片刻、确认对方收到 ACK 包后才能进入 CLOSED 状态。那么,要等待多久呢?

数据包在网络中是有生存时间的,超过这个时间还未到达目标主机就会被丢弃,并通知源主机。这称为 报文最大生存时间(MSL,Maximum Segment Lifetime)TIME_WAIT 要等待 2MSL 才会进入 CLOSED 状态。ACK 包到达服务器需要 MSL 时间,服务器重传 FIN 包也需要 MSL 时间,2MSL 是数据包往返的最大时间,如果 2MSL 后还未收到服务器重传的 FIN 包,就说明服务器已经收到了 ACK 包。