数据库小技能：根据信息内容建立索引，来有效地找到目标。【编址（Addressing）-＞寻址-＞访问】

公众号iOS逆向

发布于 2023-08-18 15:32:53

1590

发布于 2023-08-18 15:32:53

文章被收录于专栏：iOS逆向与安全iOS逆向与安全

引言

头脑就相当于是一个大数据库，我们在笔记本上写下今天要做的事情，好比是建立了索引，是提高效率的好办法。

I 编址（Addressing）->寻址->访问

1.1 编址：使用编号代替了实际的对象

计算机从一诞生开始就是要处理大量的数据的，把计算当作手段，实现一些功能。

编址：为了实现复杂的功能，对机器来讲，最简单的方法就是把所有要计算的对象都编上号，使用编号代替了实际的对象。

编址的实现方式：对数据进行连续编号，通过编号来确定数据在存储设备上的位置。通常采用物理地址的方式，即用数据在存储系统中的物理位置作为其编号，可以快速地定位数据的物理位置。

编址的缺点：在删除或插入数据时需要重新整理所有数据的地址，会造成大量的时间和空间浪费。

编址的好处：

没有编号，就无从建立索引。
用一个数学模型把计算机描述清楚，如同我们可以用变量x、y、z把一个数学公式描述清楚一样。

计算复杂的问题时，就要先写数学公式，再代入数字。

在图灵机模型中，所用的数字都放在一个个编了号（地址）的格子里。计算机对于数据的操作，都是先找到盒子的地址，然后把那个盒子中的数据拿出来处理，处理完的内容，再放回到某个地址中。

在计算机里面所有的东西都被编了号，这包括一个个的内存格子、接口、各种设备。对于这些编号，我们广义地称之为地址。计算机处理的信息，运行的指令，也都被编了号。

编号的设计和实现方法特别重要：用最少的信息，将所有的东西编号。

1.2 寻址

根据东西的特征把它的地址找到。

1.3 访问

编址是为了确定内存中数据的物理位置，而访问则是在程序运行时读取数据或写数据到存储器中。

II 查找

2.1 顺序查找

应用场景：文本替换

例如，在编辑文章时，把“北京”全都替换成“上海”。

2.2 字典查找法

字典查找法：大约估摸着所要查的字所在的位置，直接打开那一页，如果发现要找的字在这一页的前面，就往前翻，否则就往后翻，几次之后，就能找到目标。

计算机中的字典只有0和1，对应的查找方法叫二分查找（Binary Search）。查找目标时，不断缩小范围，每次减少一半。字典查找法比二分查找方法更快。

二分查找的前提（缺点）：数据要事先排序，数据是静态的。

相比查找，排序的速度要慢得多。排序是有成本的，是否应该对数据排序，要看具体应用的情况而定。

应用场景：当数据的查找次数（频次）足够多，且数据是是静态的、不能修改的的，例如学号。

通过次数抵消掉它的边际成本，为此花一些时间排序才合算。

如果数据总是在变化，可以利用原来数据有序的特点，动态调整新数据的，让每次排序所做的工作不要太多。

利用了堆的性质来进行排序：https://blog.csdn.net/z929118967/article/details/131809460?spm=1001.2014.3001.5501 堆排序分为两个主要步骤：建堆和排序。 建堆的过程是将待排序的数组构建成一个二叉堆，通常使用最大堆（大顶堆）来进行排序。 排序的过程是不断地从堆顶取出最大值（根节点），将其与堆中最后一个元素交换，然后重新调整堆，使得剩余元素仍满足堆的性质。

III 索引

索引：将数据的关键字与其在存储设备上的位置建立映射关系，通过关键字来定位数据。索引的实现方式：可以是基于排序的，也可以是基于哈希的。

排序的索引需要对数据进行排序，需要较多的时间和空间。哈希的索引通过散列函数将关键字映射到一个地址，可以快速地定位数据。但是，哈希的索引可能会出现哈希冲突，需要使用解决冲突的方法。

建索引的好处：不需要进行排序，也可以快速查找到所需要的信息。

建索引的成本：空间成本、时间成本。

空间成本：如果计算机的内存不够大，索引内容占用多了，软件速度会成倍下降。
时间成本：如果内容是变化的，要想让索引和计算机里面的内容保持一致，就要不断运行建索引的程序，让计算机慢了很多。

3.1 图书的关键词索引

图书的关键词索引中，会列举出主要关键词在书中的位置。

比如写清楚了“工号：iOS逆向”这个词出现在书中第2~6页，8~11页和33页。

3.2 计算机里的索引

和图书的关键词索引类似，都保存着所要找的信息的位置。如果所要找的信息不止一条，它会保留所有的位置。

和图书关键词索引不同的是，书后面关键词的索引只有一种，而计算机里的索引常常需要根据应用场景建立很多种，以便按照不同门类的信息进行查找。

案例：户籍数据库对每一个人的记录编好号，相当于书的页码。人名索引的每一行存储的是名字和这个名字的所有人的信息记录编号。例如，张楠是数据库中编号20230210到第20260902的人。

查询所有叫张楠的人，先在索引中找到张楠这一行，然后根据索引的指示，到数据库中，直接调出第20230210到第20260902个记录即可。

3.3 网页搜索

在网络上所有能找到的内容（文档、图片、视频）下载以后，对每一个词建立索引，记录下来每一个词都出现在哪一篇文档（网页）中的哪一些具体的位置。

Google在建索引时，是对所有的词建索引，对所有语言，所有文字建一个统一的索引，以保证我们要找的东西能够找到。

如果搜索一个长句子，搜索引擎会先把它分割成一个个独立的词，然后根据每一个词的索引，找到这个句子。

IV 数据库索引

4.1 索引无效的情况

where 子句的查询条件里有!=，将无法使用索引。
where 子句使用了 Mysql 函数的时候，索引将无效。
Where子句中使用IS NULL或者IS NOT NULL，索引将无效。
使用了反向操作，索引将不起作用。
使用 LIKE 迕行搜索匹配的时候，后模糊匹配才能让索引有效。

'xxx%'

不匹配的数据类型，不使用索引。

如果列类型是字符串，要在条件中将数据使用引号引用起来。

在WHERE中使用OR时，有一个列没有索引，那么其它列的索引将不起作用。

只能将or条件中的每个列都加上索引，必须是独立索引。

关联字段只有联合索引时不生效

超过3个join的复杂SQL，需要join的字段，数据类型保持绝对一致并保证被关联的字段有单独的索引。

4.2 创建索引

https://blog.csdn.net/z929118967/article/details/129803014

超过3个join的复杂SQL，需要join的字段，数据类型保持绝对一致并保证被关联的字段有单独的索引。（关联字段只有联合索引时不生效）
联合索引遵循最左原则
当Where 条件和 order by 子句作用在不同的列上，建立联合索引可以避免Using filesort的产生
商户级别的数据量比较大，推荐商户IDmerchant_id和代理商IDfacilitator_id创建索引。

        create index I_MKT_BOUNTY_ACTIVITY_MERCHANT_MERCHANT_ID
        on mkt_bounty_activity_merchant (merchant_id );

        create index I_MKT_BOUNTY_ACTIVITY_MERCHANT_FACILITATOR_ID
        on mkt_bounty_activity_merchant (facilitator_id );
        
        create index I_MKT_VOUCHER_ACTIVITY_STOCK_ID
        on mkt_voucher_activity (stock_id);
        
create index IX_TRADEDATE_MERCHANTID
    on trans_flow_202304 (trade_date desc, merchant_id desc, facilitator_top_id asc, facilitator_id asc);

create index Index_MarketAdjustmentActivityPartakeMerchanterLog_SID_ActCode
    on mkt_adjustment_activity_partake_merchanter_log (merchant_id, activity_code);

    create index IX_TRADENO
    on trans_flow_activity_202304 (trade_no);

4.3 删除索引（ drop index ）

# drop index Index_MarketAdjustmentActivityPartakeMerchanter_FacIdTop_ActCode on mkt_adjustment_activity_partake_merchanter ;

4.4 执行计划（explain）

 explain select  * from trans_flow_202304 where out_trade_no ='1' order by out_trade_no desc;;

利用上了索引来进行查找type: ref 表示引用查找, key_len: 259 表示索引长度为259。

type: ALL表示全表查找, key_len: NULL 表示没有索引

V 编址和索引的联系与区别

5.1 联系

编址和索引都是用来定位数据存储位置的方法，但实现方式不同。

编址是指对数据进行连续编号，通过编号来确定数据在存储设备上的位置。通常采用物理地址的方式，即用数据在存储系统中的物理位置作为其编号，可以快速地定位数据的物理位置。但是，编址的缺点是在删除或插入数据时需要重新整理所有数据的地址，会造成大量的时间和空间浪费。

索引是指将数据的关键字与其在存储设备上的位置建立映射关系，通过关键字来定位数据。索引可以是基于排序的，也可以是基于哈希的。排序的索引需要对数据进行排序，需要较多的时间和空间。哈希的索引通过散列函数将关键字映射到一个地址，可以快速地定位数据。但是，哈希的索引可能会出现哈希冲突，需要使用解决冲突的方法。