1. A data processing apparatus, comprising: a processor configured to execute instructions including branch instructions; a prefetch unit configured to prefetch instructions from memory prior to sending those instructions to the processor for execution; a branch target cache structure having a plurality of entries, each entry configured to store branch instruction information, said branch instruction information comprising an address identifier for a branch instruction executed by said processor and at least target address information associated with that branch instruction; said prefetch unit being configured, using an address of a currently prefetched instruction, to initiate a lookup operation within said branch target cache structure in order to determine if a hit condition is present, said hit condition being present if the address identifier stored in one of said plurality of entries matches with the address of the currently prefetched instruction, and in the presence of said hit condition the prefetch unit being configured to receive said at least target address information from the entry giving rise to the hit condition; said branch target cache structure comprising an initial entry branch target cache having a first number of entries, and a promoted entry branch target cache having a second number of entries, said first number of entries and said second number of entries collectively forming said plurality of entries of the branch target cache structure; the branch target cache structure being configured such that said initial entry branch target cache and said promoted entry branch target cache are accessed in parallel during said lookup operation; the data processing apparatus further comprising allocation circuitry configured, for a branch instruction executed by the processor that does not currently have a corresponding entry in the branch target cache structure, to perform an initial allocation operation to allocate one of the entries in the initial entry branch target cache for storing the branch instruction information for that branch instruction; and the allocation circuitry further being responsive to detection of a promotion threshold condition in relation to one of the entries in said initial entry branch target cache, to perform a promotion allocation operation to migrate the branch instruction information from that entry of the initial entry branch target cache to an allocated entry of the promoted entry branch target cache.