day04:坚持学小知识的第四天

1. 聚簇索引与非聚簇索引

   聚簇索引：按照每张表的主键构造一棵B+树，同时叶子节点中存放的是整张表的行记录数据，也将聚簇索引的叶子节点称之为数据页。

   优点：

   • 数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快

   • 聚簇索引对于主键的排序查找和范围查找速度非常快

     缺点：

   • 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键

   • 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。

   • 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。

   非聚簇索引：其叶子节点存储的不再是行的物理位置，而是主键值。通过非聚簇索引首先找到的是主键值，然后再通过主键值找到数据行的数据页，再通过数据页中的Page Directory找到数据行。

2. MySQL中select的执行顺序

   FROM-->ON-->JOIN-->WHERE-->GROUP BY-->HAVING-->SELECT-->DISTINCT-->ORDER BY-->LIMIT

   ① from 对查询指定的表计算笛卡尔积

   ②on 按照 join_condition 过滤数据

   ③join 添加关联外部表数据

   ④where 按照where_condition过滤数据

   ⑤group by 进行分组操作

   ⑥having 按照having_condition过滤数据

   ⑦select 选择指定的列

   ⑧distinct 指定列去重

   ⑨order by 按照orderbycondition排序

   ⑩limit 取出指定记录量

3. 面试的小收获

   • 表扬面试官，真不错，不懂的能一点点引导，虽然结果不怎么样，但是过程中还是学到点东西的，一点点就足以，开心。

   • 数组底层如何进行查询的？

     数组的内存空间是连续的，计算机会给每个内存单元分配一个地址，并且可以使用该地址来访问内存中的数据。

     使用下标访问对应的元素的原因是在内存中，数组的数据连续存放，数据长度固定，使用数组开头位置和偏移量就可以直接算出数据地址。

   • 什么场景下会考虑使用HashMap这种数据结构？HashMap查询的时间复杂度范围？

     场景：数据访问次数多的时候，因为HashMap的查询效率很高。

     时间复杂度：理想情况下O(1)，最差情况O(N)，红黑树的情况O(logn)，介于O(1)与O(N)之间。

   • Redis中的Hash数据类型，什么情况下使用？

     Redis hash 是一个 string 类型的 field（字段） 和 value（值） 的映射表，hash 特别适合用于存储对象。

   • 想实现一个五子棋游戏，你会考虑使用什么数据结构？

     使用二维数组存棋牌，然后对棋盘中的坐标值进行相关操作。

算法练习

1. 快速排序 【降序】

2. 看书：数据结构与算法分析 1.3 之前