MySQL select with between optimization
Your conditions are searching for ranges. Now imagine you're looking in a dictionary and looking up all words where the first letter is "greater" than A. Of how much use is the index? You want to narrow the search range down as much as possible. MySQL most of the time can only use one index per table. Combine those begin and end indexes.

CREATE TABLE `geo_ip_city` (
    `id` INT(5) UNSIGNED NOT NULL AUTO_INCREMENT,
    `begin` BIGINT(20) NOT NULL DEFAULT '0',
    `end` BIGINT(20) NOT NULL DEFAULT '0',
    `code` VARCHAR(2) NOT NULL DEFAULT '',
    `city` TINYINT(3) UNSIGNED NOT NULL DEFAULT '0',
    PRIMARY KEY (`id`),
    INDEX `idx_begin_end` (`begin`, `end`)
);


I also removed the index on code because it's also pretty much useless. It consists of two letters. Assuming there are no special characters/symbols included, this leaves you with 26*26=676 possible values for this column. That's a selectivity of 676 / 4.500.000 = 0.0001. You want to have the selectivity as near to 1 as possible.