【Day 16】InnoDB indexing

这是我很喜欢的主题，但今天依旧不舒服而且我队友不安ㄌ只好先断尾求生

InnoDB

InnoDB 是资料库引擎，
因为支援 Transaction，目前是 MySQL 的预设引擎。（早期是 MyISAM）
[[这里补张 dbms的结构图好ㄌ]]
以我目前的认知，不同存储引擎的差异主要在於「indexing」

Indexing

有上过资料结构都知道，一堆资料如果要查询效率高，最好是排序过。
这就是为什麽需要做索引了，
其实就只是把会常常查询的那个 column 拿出来，并以此 column 数值来排序所有的 records。

clustered index

• primary key
• 资料实际上就是依照这种 index 排序

non-clustered index（secondary index）

• 通常人家说做 indexing 会比较快，是指这种 index
• 如果表中有常会需要拿来查询比较的 column（attribute），拿出来做 non-clustered index
• 做出另一棵依照此 column 排序的树，查询出的数值为 clustered index，再去存放所有资料的那棵树以 clustered index 取需要的资料
• 其实我觉得称 secondary index 更容易懂，用二级索引查出主索引，再取得资料

如果再讲底层一些，densed indexing 与 multilevel-indexing

densed indexing

今天存资料到硬碟上，根据 table schema 每条资料会占用一定大小，
这样查询资料会很费时。

因此我们需要一个表纪录 index + 属於这个 index 的资料在哪，
而这个 index 表每条资料的大小应该会比原来的 table 小，
这样载入到记忆体中时，同样大小可以知道更多「资料在哪」的资讯。

所以如果今天 column 很少，或许就没有额外做 densed indexing 的必要呢

multilevel-indexing

如果资料变多，densed index 一直增加下去，O(n) 的 n 越来越大也不是办法。
那就多增加几层吧，类似 virtual memory 的 multi-level page table 的概念。

clustered/non-clustered index vs multilevel-indexing

我觉得主要差在作用层次与目的。

• clustered / non-clustered 是高层次存资料时「开发者」可以做的选择。
• multilevel-indexing 是底层存储到硬碟上，为避免 index 增长太大，以减少 IO 次数的方法。
  两者都是由 sparsed index 查出真正的 densed index，再去最上层的表取值。

B tree B+ tree

而有某种程度的「排序」+「动态删减」的资料结构，就会想到 binary tree，
B tree 和 B+ tree 可以说是 binary tree 的延伸变种。

什麽时候做 indexing？

索引说白了就是以空间换搜寻时间提升，所以不能每个 column 都做索引。

• primary key (定义 table 时应该就要写好）
• foreign key
• 常常查询的栏位（ORDER BY / WHERE / GROUP BY）
  建立索引表除了需要空间，每次新增删除等操作，都要额外花时间去索引表作更动（想像要去树上新增删除节点）