5.5.4:

(test) > explain select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591689;
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
|  1 | SIMPLE      | test  | range | borders       | borders | 4       | NULL | 2700 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
1 row in set (0.00 sec)

(test) > select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591689;
+----------+
| count(*) |
+----------+
|        3 |
+----------+
1 row in set (0.00 sec)

(test) > 
(test) > explain select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591759;
+----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+
|  1 | SIMPLE      | test  | range | borders       | borders | 4       | NULL | 34200 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+
1 row in set (0.00 sec)

(test) > select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591759;
+----------+
| count(*) |
+----------+
|       38 |
+----------+
1 row in set (0.00 sec)

(test) > 
(test) > explain select count(*) FROM test WHERE b_left BETWEEN 2591659 AND 2609114;
+----+-------------+-------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows   | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+--------------------------+
|  1 | SIMPLE      | test  | range | borders       | borders | 4       | NULL | 434576 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)

(test) > select count(*) FROM test WHERE b_left BETWEEN 2591659 AND 2609114;
+----------+
| count(*) |
+----------+
|     8727 |
+----------+
1 row in set (0.01 sec)




5.1.48:

mysql> explain select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591689;
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
|  1 | SIMPLE      | test  | range | borders       | borders | 4       | NULL |    3 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
1 row in set (0.00 sec)

mysql> select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591689;
+----------+
| count(*) |
+----------+
|        3 |
+----------+
1 row in set (0.00 sec)

mysql>
mysql> explain select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591759;
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
|  1 | SIMPLE      | test  | range | borders       | borders | 4       | NULL |   38 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
1 row in set (0.00 sec)

mysql> select count(*) FROM test WHERE b_left BETWEEN 2591685 AND 2591759;
+----------+
| count(*) |
+----------+
|       38 |
+----------+
1 row in set (0.00 sec)

mysql>
mysql> explain select count(*) FROM test WHERE b_left BETWEEN 2591659 AND 2609114;
+----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+
|  1 | SIMPLE      | test  | range | borders       | borders | 4       | NULL | 23528 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+
1 row in set (0.00 sec)

mysql> select count(*) FROM test WHERE b_left BETWEEN 2591659 AND 2609114;
+----------+
| count(*) |
+----------+
|     8727 |
+----------+
1 row in set (0.00 sec)