I'm trying to diagnose seemingly random performance issues with our database server. Below is a simplified scenario, hopefully generic enough to serve as a useful future reference for anyone looking for the same answer. 

Suppose I have a (MySQL 5.6 w/ InnoDB) table like

```
CREATE TABLE Example (
    id INT NOT NULL AUTO_INCREMENT,
    secondary_id INT DEFAULT NULL,
    some_data TEXT NOT NULL,
    PRIMARY KEY (id),
    KEY (secondary_id)
) ENGINE=InnoDB;

```

with about 15 million rows. However, the `secondary_id` column is `NULL` for almost all rows, so the index on `secondary_id` has very, very low cardinality (in our case about ~30k). In our case, when we experience the performance issue I'm investigating, the process list for the server shows many (100+) queries of the form:

```
UPDATE Example SET secondary_id = NULL, some_data = '...' WHERE id = 123;

```

that are taking ~90+ seconds to complete, during which they are in the ["updating" state](https://dev.mysql.com/doc/refman/5.6/en/general-thread-states.html). (These queries would be running in separate transactions.)

I'm specifically wondering if the transition from a not-null `secondary_id` to a null `secondary_id` is causing performance slowdowns in the above `UPDATE`. That is, is it possible that updating the index in this case takes a significant amount of time since there are so many rows (~15mil) that have the same value for that column (`NULL`)? 

I guess this question stems from me not understanding how the B+Tree index will store row pointers for rows having duplicate index values. I'd guess that node would have a linked list (or something similar) with a pretty fast insertion time, so I'd guess the answer to my question is "No". But I'd like to confirm that with the experts, i.e. you all. 

I've tried to do a fair amount of research here, but I've come up pretty empty handed. Probably the most comprehensive post is [this one](http://hackthology.com/lessons-learned-while-implementing-a-btree.html), which explains some different techniques for handling duplicate keys, but I'm specifically looking for InnoDB/MySQL's approach.