钛节点

基础查找之索引入门

发表@2018-09-13 09:15:22

更新@2023-01-21 22:47:40

前面铺垫了这么久，终于熬到这一章节了！学了那么多基础数据结构和简单算法，为的是什么？！

来，大声告诉我，为的是什么！

![](https://ti-node.com/static/upload/6415366782038573057)

当然能！！！比如下面这位，就娶到了一位美丽善良的亚裔，可谓成功典范：

![](https://ti-node.com/static/upload/6415367274575691776)

看到这个，泥，还在犹豫什么？

其实说到底，搞这么多枯燥的玩意为的就是用，我的精神领袖王守仁曾经说过“知行合一”，我的精神导师毛泽东也说过“实践是检验真理的唯一标准”。

作为和我一样的蠢货青年，在面试的时候常被人问到：“mysql有几种存储引擎？”、“索引有几种类型？”，如果是这两个问题，那就还好，路上已经背诵的差不多了，可以操作一波儿应付一下，结果，人家又问：“索引优化有什么经验吗？”，使劲想回忆，结结巴巴背诵了几点网上抄来抄去的那几条金科玉律，本以为可以蒙混过关了，结果人家放大招了：“尝试通过原理解释一下为什么这样优化索引”

![](https://ti-node.com/static/upload/6345443000872599553)![](https://ti-node.com/static/upload/6345443000872599553)![](https://ti-node.com/static/upload/6345443000872599553)![](https://ti-node.com/static/upload/6345443000872599553)![](https://ti-node.com/static/upload/6345443000872599553)![](https://ti-node.com/static/upload/6345443000872599553)

今天，我们尝试自己实现最简单粗暴入门的索引，从而循序渐进地继续深入探讨。首先，我们做一个简单的数据库系统，功能就是记录姓名、年龄和性别，我们将数据以json格式存储到一个文本文件中，大概类似于下面这样：

[{"name":"user9351","age":45,"gender":2},{"name":"user1768","age":71,"gender":2}]

我们将100000个人存入到这个文本文件中，如何制造这个json数据我就不讲了，你们自己操作。下面问题来了，就是我要从中找到某个用户，比如user5555（当然了，你得保证其中一定有这个用户），那么我们的做法大概如下：

```php
<?php
/*
$user_suf_arr = [];
for( $i = 1; $i <= 100000; $i++ ){
  $user_suf = mt_rand( 1, 2000000 );
  // 如果在数组中
  if( in_array( $user_suf, $user_suf_arr ) ){
    echo '重复，回滚'.PHP_EOL;
    // 回滚   
    $i--;
    continue;
  } 
  $user_suf_arr[] = $user_suf;
  $user[] = [ 'name' => 'user'.$user_suf, 'age' => mt_rand( 1, 100 ), 'gender' => mt_rand( 1, 2 ), ];
}
$user = json_encode( $user );
file_put_contents( './user.json', $user );
exit;
 */
 
 $begin_time = microtime( true );
 // 读取数据
$user = file_get_contents( './user.json' );
$user = json_decode( $user, true );
// 假如很短时间内500个人并发查询
// 查找同一个用户名不会有缓存，所以不用考虑缓存影响速度的问题
for( $i = 1; $i <= 500; $i++ ){
  foreach( $user as $user_item ){
    if( 'user1692145' == $user_item['name'] ){
      //echo '找到了'.PHP_EOL;
    }   
  }
}
$end_time = microtime( true );
echo '耗费时间'.( $end_time - $begin_time ).PHP_EOL;
```

保存后运行一把，我这里机器显示如下：

![](https://ti-node.com/static/upload/6415391831957176321)

短时间内500个查找用5.6秒钟多，要是流量再大点儿，而且用户找的数据分布都偏后半部分，这个成绩一定会更差。所以，作为有为青年就会考虑使用一种如何加速查找。观察了一下name字段的数据特点，那就是前四个字母是固定的，后缀数字是随机且唯一的，于是打算将后缀数字和用户在数组中的位置偏移量做个对应关系，大概如下所示：

user数字后缀 =》 user信息在数组中的index偏移量

然后，将改数组以user数字后缀为关键列从小到大排列一下，保存起来。以后当有人查找user1312312的时候，就会通过二分查找直接从“user数字后缀 =》 user信息在数组中的index偏移量”映射表中去查找1312312，从而我们可以获取到user1312312在user数组中的偏移量，有了偏移量我们就能以O(1)时间复杂度获取到想要的用户信息了！

其实，这就是一种简单的索引技术了！只不过，此处索引的维护建立我们依靠了php的数组数据结构，有投机取巧之嫌，但道理是这样的摆在这里了，重在理解吧。有能力的同学，可以通过C语言等来自己实现索引会更好一些。

心动，不如行动！

```php
<?php
/*
$user_suf_arr = [];
for( $i = 1; $i <= 100000; $i++ ){

// 随机一个数值 user后缀
  $user_suf = mt_rand( 1, 2000000 );
  // 如果在数组中
  if( in_array( $user_suf, $user_suf_arr ) ){
    echo '重复，回滚'.PHP_EOL;
    // 回滚
    $i--;
    continue;
  }
  $user_suf_arr[] = $user_suf;

$user[ $i ] = [ 'name' => 'user'.$user_suf, 'age' => mt_rand( 1, 100 ), 'gender' => mt_rand( 1, 2 ), ];
	$uid_index_arr[ $user_suf ] = $i;
  	
}
$user = json_encode( $user );
file_put_contents( './user.json', $user );
file_put_contents( './user.index.json', json_encode( $uid_index_arr ) );
exit;
 */

$begin_time = microtime( true );
// 读取数据
$user = file_get_contents( './user.json' );
$user = json_decode( $user, true );
// 读取索引
$index = file_get_contents( './user.index.json' );
$index = json_decode( $index, true );
// 假如很短时间内500个人并发查询
// 查找同一个用户名不会有缓存，所以不用考虑缓存影响速度的问题
for( $i = 1; $i <= 500; $i++ ){
  $suf = substr( 'user1948829', 4 );
	// 在索引文件中查找对应关系
	$_index = $index[ $suf ];
	$_user = $user[ $_index ];
	echo $_user['age'].PHP_EOL;
}
$end_time = microtime( true );
echo '耗费时间'.( $end_time - $begin_time ).PHP_EOL;
```

代码保存后执行，我们看到如下：

![](https://ti-node.com/static/upload/6415406210090008576)

进步神速！

但是，代价也是有的，首先就是我们还需要额外浪费磁盘空间去维护一个索引文件，其次是如果有新的数据加入或者删除，这个索引文件就必须要重新更新一下。只不过相对于速度的提升程度，这点儿额外的代价都不算什么了，利益远远大于损失。

在结束前，放点儿需要背诵或者眼熟的内容：一般说来，索引根据类型可以分成线性索引、树型索引、多级索引。我们今天案例中简单这个算是线性索引。线性索引有个巨大的缺点，就是有多少条数据就需要对应多少条索引记录。而树型索引就比较屌了，我们常说的mysql数据库中的一些索引，本质上就是树型索引。