BINARY(16) занимает 16 байт, а CHAR(16) занимает 16 символов. Если кодировка этого поля однобайтная (например, latin1), то размер индекса будет тоже 16 байт, а если, например, utf8, то 16 × 3 = 48 байт. Ну и короткие индексы работают, разумеется, быстрее.