【讨论中】mysql的loose index

flycms

最近看mysql手册，看上边对于松散索引扫描和紧凑索引扫描的解释，很让我迷惑，

松散扫描如下
[code]
    通过该访问方法，MySQL使用某些关键字排序的索引类型(例如，B-树)的属性。该属性允许使用 索引中的查找组而不需要考虑满足所有WHERE条件的索引中的所有关键字。既然该访问方法只考虑索引中的关键字的一小部分，它被称为松散索引扫描。如果没有WHERE子句， 松散索引扫描读取的关键字数量与组数量一样多，可以比所有关键字数小得多。如果WHERE子句包含范围判断式， 松散索引扫描查找满足范围条件的每个组的第1个关键字，并且再次读取尽可能最少数量的关键字。

紧凑索引扫描

    对于引用GROUP BY关键字元素的前面、中间关键字元素的查询中的所有列，有一个常量等式条件即足够了。等式条件中的常量填充了搜索关键字中的“差距”，可以形成完整的索引前缀。这些索引前缀可以用于索引查找。如果需要排序GROUP BY结果，并且能够形成索引前缀的搜索关键字，MySQL还可以避免额外的排序操作，因为使用有顺序的索引的前缀进行搜索已经按顺序检索到了所有关键字。


看飘红文字，既然补齐了完整的索引前缀，为什么就不能使用btree的属性-》在松散索引扫描中提到的查找组，求指导，我已经拿出数据结构的书再找了但找不到合理的解释！本人对这些数据结构完全自己看的，可能是理解的不正确，请过来人解释一下这个问题！

zhangshengdong

从内部理解是很辛苦的。

我从全局去理解松散和紧凑索引

松散,只要scan一部分的group_id,就可以找到你要的数据
紧凑,需要scan全部的group_id,才能找你你要的数据

例子：
EXPLAIN SELECT actor_id, MAX(film_id)
FROM film_actor
Where actor_id <102
GROUP BY actor_id\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: film_actor
         type: range
possible_keys: NULL
          key: idx_actor_film_id
      key_len: 4
          ref: NULL
         rows: 1004
        Extra: Using index for group-by
1 row in set (0.00 sec)



EXPLAIN SELECT actor_id, MAX(film_id)
FROM film_actor
Where actor_id =101
GROUP BY actor_id\G

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: film_actor
         type: ref
possible_keys: idx_actor_film_id
          key: idx_actor_film_id
      key_len: 4
          ref: const
         rows: 4095
        Extra: Using index
1 row in set (0.00 sec)


我这里示例的数据就是actor_id=101和102的相关数据。

明显可以看出，松散只找了1004行
                   而紧凑找了4095行

我认为这是它们比较明显的区别，也可以看出松散比紧凑快。

至于算法是如何实现的？数据结构的BTree树是怎样的？还没有时间去理解和深究，如有高手出来，说出一二。

或者反驳我的观点，我非常开心，以上是我的愚见。

flycms

谢谢，我明白您的意思，您把第一个actor_id <102改成actor_id=102,现在只有group by条件不同，但是actor_id=2已经补齐了这个最左前缀索引，用到btree的属性“允许使用 索引中的查找组而不需要考虑满足所有WHERE条件的索引中的所有关键字”，那后一种情况下也应该可以去到分好组的关键字吧，为什么一定要扫描所有符合条件的关键字呢。

flycms

from http://stackoverflow
Some implementations simply concatenate the values in the order of the columns, with delimiters.
[简单的按顺序连接各列得值，用分隔符隔开]

Another solution is to simply have a b-tree within a b-tree. When you hit a leaf on the first column, you get both a list of matching records and a mini b-tree of the next column, and so on. Thus, the order of the columns specified in the index makes a huge difference on whether that index will be useful for particular queries
[另一个方案是用一个btree索引另一个btree,当你检索到一个第一列的一个叶子节点时，你会得到一个比较小的数据集以及相匹配的下一个列的btree，以相同方式检索下一列。所以索引中声明的列的顺序对查询能不能使用索引的影响比较大]